二分查找
by.Qin3Yu
本文需要读者掌握 顺序表 的操作基础，完整代码将在文章末尾展示。
顺序表相关操作可以参考我的往期博文：
【C++数据结构 | 顺序表速通】使用顺序表完成简单的成绩管理系统.by.Qin3Yu
文中所有代码使用 C++ 举例，且默认已使用部分头文件和 std 命名空间：
#include <iostream>
#include <vector>
using namespace std;
概念速览
二分查找概述
- 二分查找 算法属于 搜索算法 的一种。它是一种高效的搜索算法，用于在有序数组或列表中查找特定元素的位置。
- 二分查找的基本思想是通过将目标值与数组中间的元素进行比较，从而将搜索范围缩小一半。如果目标值小于中间元素，则继续在左侧子数组中进行二分查找；如果目标值大于中间元素，则继续在右侧子数组中进行二分查找；如果目标值等于中间元素，则直接返回该位置。通过重复这个过程，最终可以找到目标值或确定其不存在于数组中。
- 二分查找算法的时间复杂度为 O(log n) ，且不需要额外存储空间。
二分查找通常被使用于符合以下条件的以下场景：
- 数组或列表是 有序 的；
- 静态 数据结构；
- 数据量较 大 ；
- 只需要 快速确定 元素是否存在。
算法详解
逻辑解析
- 二分查找，就是不断的对搜索范围进行折半，从而缩小搜索范围，我们用下面的数组来进行说明：
- 在上面的有序数组中，我们要查找数组内是否存在值 31 ，于是我们可以如下图所示，使用三个指针，一个指向数组的最左端，一个指向数组的最右端，一个指向数组的中间。
- 我们使用 left 、right 、mid 分别表示左、右、中指针，当前 mid 指向的值为 26 ，因为数组是有序数组，所以可以得知，我们要查找的值 31 一定在 26 的 右侧 ，因此，我们将左指针 left 指针指向 mid 的后一位元素，然后重新计算出 mid 指针的位置：
- 如图所示，当前 mid 指向的值为 44 ，比 31 小，因此我们要查找的 31 一定在 44 的左侧，因此，我们把右指针 right 指向 mid 的前一位元素，然后重新计算 mid 的位置：
- 同理，mid 指向的值 30 小于 31 ，所以我们把 left 移到 mid 的后一位，然后重新计算 mid 的位置：
注意：在二分查找中，right 与 left 重合属于正常现象，表示搜索范围只有一个数字。
- 此时，我们再检查 mid 所指的值，就是我们要查找的 31，于是我们返回出对应的结果，表示成功查找到元素。
- 我们在上一步的例子中做出一点修改，假如数组中没有我们要查找的值 31 ，则会产生一种情况，即 left 跑到 right 的右边，代表数组中没有我们要查找的元素：
代码实现
- 在下例中，我们使用 vector 顺序表来保存数据，然后使用 binarySearch 方法表示二分搜索：
int main() {
vector<int> data = {1,7,9,11,14,19,20,26,29,30,31,44,45,52,59};
int target = 31;
int result = binarySearch(data, target);
}
- 首先，我们要声明左右指针，左指针指向数组最前端，即索引为 [0] ，右指针指向数组最右端，即索引为 [长度-1] ：
int left = 0;
int right = arr.size() - 1;
- 在上文中我们提到，如果 left 指针移动到了 right 指针右边，则代表数组内没有对应的值，则返回 -1 ，表示没有目标值：
while (left <= right) {
...
}
return -1;
- 接下来，我们要根据左右指针计算出中间指针 mid ，即左指针加上两指针之和除二：
int mid = left + (right - left) / 2;
- 最后，我们来判断 mid 指针所指值与查找值的关系，如果相等，则返回成功目标值的索引：
if (arr[mid] == target) {
return mid; // 找到目标，返回索引
}
- 如果 mid 所指值比目标值小，则证明目标值只可能在 mid 右边，我们将 left 指针移到 mid 指针后一位，从右侧子数字开始查找：
else if (arr[mid] < target) {
left = mid + 1; // 继续在右侧子数组中查找
}
- 相反，如果 mid 所指值比目标值大，则证明目标值只可能在 mid 左边，我们将 right 指针移到 mid 指针前一位，从左侧子数字开始查找：
在这里插入图片描述
else {
right = mid - 1; // 继续在左侧子数组中查找
}
- 将上述代码做出结合后，便是完整的二分查找代码，具体如下文所示。
完整算法代码
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止(left + right)出现溢出
if (arr[mid] == target) {
return mid; // 找到目标，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 继续在右侧子数组中查找
} else {
right = mid - 1; // 继续在左侧子数组中查找
}
}
return -1; // 没有找到目标，返回-1
}
int main() {
vector<int> data = {1,7,9,11,14,19,20,26,29,30,31,44,45,52,59};
int target = 31;
int result = binarySearch(data, target);
if (result != -1) {55
cout << "成功查找到对应值！" << result << endl;
} else {
cout << "找不到对应值。" << endl;
}
return 0;
}
