二分查找c++
时间: 2023-07-01 15:22:54 浏览: 44
二分查找(Binary Search)是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是:每次取中间位置的值与目标值进行比较,如果中间位置的值比目标值大,则在左半部分继续查找;如果中间位置的值比目标值小,则在右半部分继续查找,直到找到目标值为止。
下面是C++实现二分查找的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
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;
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 5;
int index = binarySearch(nums, target);
if (index != -1) {
cout << "Target found at index " << index << endl;
} else {
cout << "Target not found" << endl;
}
return 0;
}
```
在此示例中,我们定义了一个名为`binarySearch`的函数,它接受一个有序数组和目标元素作为参数,并返回目标元素在数组中的索引。我们使用`left`和`right`两个指针来跟踪搜索范围的左右边界。在每次迭代中,我们计算中间位置的索引`mid`,并将其与目标元素进行比较。如果中间元素等于目标元素,则返回其索引。如果中间元素小于目标元素,则将搜索范围缩小到右半部分。如果中间元素大于目标元素,则将搜索范围缩小到左半部分。如果搜索范围缩小到左边界大于右边界,说明目标元素不在数组中,返回-1。
希望能帮到你!