用C++实现给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
时间: 2024-02-27 13:55:09 浏览: 65
好的,这是一个简单的二分查找问题,在 C++ 中可以这样实现:
```c++
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
这个函数接受一个有序的整型数组 `nums` 和一个目标值 `target`,在 `nums` 中查找 `target`。如果找到了,返回对应的下标;否则返回 -1。
函数首先初始化左右指针 `left` 和 `right` 分别为数组的第一个和最后一个元素的下标。然后进入循环,只要 `left` 没有超过 `right`,就一直查找。
在循环中,首先计算中间元素的下标 `mid`。如果 `nums[mid]` 等于 `target`,说明找到了,直接返回 `mid`。如果 `nums[mid]` 小于 `target`,说明 `target` 在 `mid` 的右侧,将 `left` 更新为 `mid + 1`。如果 `nums[mid]` 大于 `target`,说明 `target` 在 `mid` 的左侧,将 `right` 更新为 `mid - 1`。
如果循环结束仍然没有找到 `target`,说明 `target` 不在数组中,返回 -1。
阅读全文