c++实现二分搜索算法
时间: 2024-09-19 11:09:06 浏览: 25
二分搜索算法是一种在有序数组中查找特定元素的高效搜索算法。其基本思想是从数组中间开始,如果目标值小于中间元素,则在左半部分继续搜索;如果大于中间元素,则在右半部分搜索;直到找到目标值或者搜索范围为空。
以下是C++中实现二分搜索的基本步骤:
```cpp
#include <iostream>
using namespace std;
// 函数声明
int binarySearch(int arr[], int l, int r, int x);
int main() {
int arr[] = {2, 3, 4, 10, 40}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10; // 要查找的元素
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
cout << "Element not found in array";
else
cout << "Element found at index " << result;
return 0;
}
// 二分搜索函数实现
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// 如果元素等于中间元素,返回索引
if (arr[mid] == x)
return mid;
// 如果元素小于中间元素,在左半边递归查找
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// 否则,在右半边递归查找
return binarySearch(arr, mid + 1, r, x);
}
// 没有找到,返回 -1
return -1;
}