二分查找（Binary Search）

算法原理

二分查找（Binary Search）只服务于有序序列：每步取搜索区间的中点与目标比较，要么恰好命中，要么就能确定目标只可能在其中一半——把另一半整块丢弃。搜索区间每步减半，n 个元素最多 ⌈log₂(n+1)⌉ 次比较就见分晓，这是「有序」这一前置条件换来的指数级加速。

本动画在 16 个元素的升序数组上演示两轮查找：先找 15（命中，4 步），再找 29（未命中，同样 4 步）——同是砍半，一个停在唯一亮绿，一个停在全场尽暗。

节拍（动画严格按此演示）：

1. 区间 [lo, hi] 从整个数组出发，取中点 mid = (lo+hi)/2（下取整）；
2. a[mid] == target：命中，查找结束；
3. target < a[mid]：目标只可能在左半，hi = mid - 1——中点一并弃掉；
4. target > a[mid]：目标只可能在右半，lo = mid + 1——中点同样弃掉；
5. 区间耗尽（lo > hi，两指针交叉而过）：目标不在数组中，查找以未命中结束。

动画怎么看

• 反色目标卡（画面上方悬浮）：本轮要找的值，全片唯一反色身份卡；命中时下探致意，未命中转红并浮 ✗；两轮之间数字翻转切换；
• 橙色卡：当前中点 a[mid]，卡上方有 mid 圆徽章（只在探测期存在，每轮重新落位）；
• 深绿卡（带 ✓）：命中的元素，全片仅出现一次；
• 压暗卡：已弃半区——判定后灰罩掠过、压暗封存，本轮内永不复亮；命中后其余卡保持压暗（"万物俱寂、唯余一绿"）；
• 光晕：当前搜索区间 [lo, hi]，随每砍同步收缩；
• lo / hi 圆徽章：区间两端边界，随砍半滑动；未命中时两徽章交叉并排（lo 越过 hi）即区间耗尽。

卡片下的小字是数组下标，可对照动画下方的实时解说行核对 mid=(lo+hi)/2 的算术（如 ① mid=(0+15)/2=7、① 15 < 38 ｜ hi → 6、② ✗ lo > hi）。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
using namespace std;

// 标准二分：返回 target 的下标，不存在返回 -1
int binarySearch(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {                  // 区间非空才继续
        int mid = lo + (hi - lo) / 2;   // 防溢出写法，等价 (lo+hi)/2
        if (a[mid] == target) return mid;
        if (target < a[mid]) hi = mid - 1;   // 砍右半（mid 已排除）
        else                 lo = mid + 1;   // 砍左半
    }
    return -1;                          // lo > hi：目标不在场
}

int main() {
    vector<int> a = {4, 11, 15, 19, 23, 27, 32, 38, 44, 49, 55, 61, 66, 72, 78, 84};
    cout << binarySearch(a, 15) << endl;   // 输出：2
    cout << binarySearch(a, 29) << endl;   // 输出：-1（未命中）
    return 0;
}

什么时候用二分查找

二分是「有序区间上加速定位」的通用思想：有序数组的查找、lower_bound / upper_bound、答案单调性上的二分（最小值最大化），以及「二分答案 + 贪心判定」的题型族都由它展开。使用前提只有一条——区间具有单调性（或至少可判定性）。写法上最易错的是边界：mid 是否排除、循环终止条件选 lo < hi 还是 lo <= hi。本动画的「中点一并弃掉」与「lo > hi 交叉即耗尽」正是这套边界语义的可视化——看懂这两拍，手写二分就不会再纠结边界。