789 字
2 分钟
二分详解
以下是一份关于“二分查找”的详解文档，用 Markdown 格式编写，配有 C++ 代码，解释尽量简单、口语化，避免堆砌术语。
二分查找（Binary Search）详解
一句话讲明白
二分查找就是“猜数字”游戏的最优策略：
你心里想一个 1~100 的数字，我每次猜中间的数，你说“大了”我就往左半段猜，说“小了”我就往右半段猜。这样每次都能排除一半，很快就能找到。
适用场景
- 数据必须是有序的（从小到大或从大到小）。
- 主要用来快速查找某个元素是否存在，或者找到第一个满足条件的位置。
核心思想
- 设定一个左边界
left和一个右边界right，初始时覆盖整个数组。 - 每次取中间位置
mid = (left + right) / 2。 - 比较
mid位置的值与目标值：- 如果相等，找到了，结束。
- 如果目标值比
mid小，说明目标在左半边，把right移到mid - 1。 - 如果目标值比
mid大，说明目标在右半边，把left移到mid + 1。
- 重复上述步骤，直到
left > right，说明没找到。
时间复杂度
- 每次排除一半，所以最多需要 log₂(n) 次比较（n 是元素个数）。
- 比从头到尾一个个找（O(n)）快得多。
空间复杂度
- 只用了几个变量，O(1)（常数级内存）。
基础版 C++ 代码（找某个数是否存在）
#include <iostream>#include <vector>using namespace std;
// 二分查找，返回目标值的下标，如果不存在返回 -1int binarySearch(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; // 没找到}
int main() { vector<int> arr = {1, 3, 5, 7, 9, 11, 13}; int target = 7; int result = binarySearch(arr, target);
if (result != -1) cout << "找到了，下标是 " << result << endl; else cout << "没找到" << endl;
return 0;}容易踩的坑（新手注意）
- 循环条件要写
left <= right，少写了等号可能会漏掉最后一个元素。 - 计算
mid时最好用left + (right - left) / 2，而不是(left + right) / 2，防止两个大数相加溢出。 - 数组一定要提前排好序，否则二分结果完全错误。
进阶用法：找第一个大于等于目标的位置（左边界）
有时候我们不是找“有没有”，而是找第一个满足某个条件的位置，比如插入位置。
// 返回第一个 >= target 的下标（如果所有数都小于 target，返回数组长度）int lowerBound(vector<int>& arr, int target) { int left = 0, right = arr.size(); // 注意 right 初始为 size，不是 size-1 while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] >= target) { right = mid; // 满足条件，向左缩小 } else { left = mid + 1; // 不满足，向右走 } } return left;}同样，找最后一个小于等于目标的位置（右边界）也很类似，只需要改一下判断条件。
生活中的类比
- 查字典：翻到中间，看拼音是在前面还是后面，再翻一半……
- 图书馆找书：按编号找，先看中间那架，决定去左边还是右边。
- 电商价格筛选：你想买 500 元左右的商品，系统用二分在价格排序中快速定位。
总结
- 二分查找 = 不断对半缩小范围。
- 前提：数据有序。
- 写代码记住：左右指针 + while 循环 + mid 比较。
- 学会基础版后，稍微改改条件就能用在很多变种题上。
记住一句话：
“二分的精髓不是找中间，而是每次都能扔掉一半。”
这样一想，是不是很简单？😊
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时