c++使用二分查找法举例
时间: 2024-06-15 14:06:20 浏览: 89
以下是一个使用二分查找法在C++中查找元素的例子[^1]:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int 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;
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 5;
int index = binarySearch(nums, target);
if (index != -1) {
cout << "Element found at index " << index << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
```
这个例子演示了如何使用二分查找法在一个有序数组中查找指定元素。首先,我们定义了一个`binarySearch`函数,它接受一个有序数组`nums`和目标元素`target`作为参数。然后,我们使用两个指针`left`和`right`来表示查找区间的左右边界。在每一次循环中,我们计算中间元素的索引`mid`,并将其与目标元素进行比较。如果中间元素等于目标元素,则返回中间元素的索引。如果中间元素小于目标元素,则将左边界指针`left`更新为`mid + 1`,否则将右边界指针`right`更新为`mid - 1`。如果循环结束时仍然没有找到目标元素,则返回-1表示未找到。
在`main`函数中,我们定义了一个有序数组`nums`和目标元素`target`,然后调用`binarySearch`函数进行查找。如果返回的索引不等于-1,则打印出元素找到的位置,否则打印出元素未找到的提示。
阅读全文