如何用C++实现二分查找
时间: 2023-10-27 18:03:09 浏览: 50
要实现二分查找,可以按照以下步骤进行:
1. 将有序数组作为函数参数传入
2. 定义左侧边界 left 和右侧边界 right,分别初始化为数组首项和末项的索引值
3. 取中间项 mid 的索引值:mid = (left + right) / 2
4. 比较要查找的 key 值和中间项的值 arr[mid] 的大小关系:
- 如果 key > arr[mid],说明要查找的值位于 mid 右侧,更新左侧边界为 mid + 1
- 如果 key < arr[mid],说明要查找的值位于 mid 左侧,更新右侧边界为 mid - 1
- 如果 key == arr[mid],说明已经找到,返回 mid 的索引值
5. 如果 left > right,说明没有找到,返回 -1 表示查找失败
以下是 C 语言实现二分查找的代码示例:
```c
int binary_search(int arr[], int len, int key) {
int left = 0;
int right = len - 1;
int mid;
while(left <= right) {
mid = (left + right) / 2;
if(arr[mid] == key) {
return mid;
} else if(key < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```