二分查找的算法流程c++
时间: 2024-06-22 18:02:35 浏览: 6
二分查找(Binary Search),也称为折半查找,是一种在有序数组中快速查找特定元素的搜索算法。以下是二分查找的基本算法流程,使用C++实现:
1. 初始化:首先,设置两个指针,`low`表示数组的起始位置(下标0),`high`表示数组的结束位置(下标数组长度减1)。
2. 计算中间索引:计算中间索引 `mid` 为 `(low + high) / 2`。这个公式确保了我们每次都能取到数组中间的元素。
3. 检查条件:比较中间元素的值和目标值:
- 如果中间元素等于目标值,搜索结束,返回中间索引。
- 如果中间元素小于目标值,说明目标可能在数组的右半部分,将`low`设为 `mid + 1`,然后回到步骤2。
- 如果中间元素大于目标值,说明目标可能在数组的左半部分,将`high`设为 `mid - 1`,然后回到步骤2。
4. 重复步骤2和3,直到找到目标值或`low`超过`high`,此时可以判断目标值不在数组中,返回-1。
下面是简单的C++代码示例:
```cpp
int binarySearch(int arr[], int target, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid; // 找到目标,返回索引
else if (arr[mid] < target)
low = mid + 1; // 目标可能在右半部分
else
high = mid - 1; // 目标可能在左半部分
}
return -1; // 没有找到目标,返回-1
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)