二分查找：每次排除一半

01二分查找为什么快？

如果数据已经按从小到大排列：

2  5  8  12  19  25  31  40

寻找 25 时，不需要从 2 开始一个一个看，可以先看中间位置。

02一次比较怎样排除一半？

因为数组有序：如果目标比中间值大，那么中间值左边更小的部分都不可能是目标。

03基本代码怎样写？

int left = 0;
int right = n - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (a[mid] == target) {
        return mid;
    } else if (a[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

return -1;

04为什么 mid 不直接写 (left + right) / 2？

数学上看起来一样，但 left + right 在某些整数范围下可能先溢出。

left + (right - left) / 2

是常见的更稳妥写法。

05二分查找必须满足什么条件？

这里这种二分查找必须依赖数据有序。

06有重复元素时会找到哪一个？

普通“找到就返回”的二分查找，只保证找到某个匹配位置，不保证一定是第一个或最后一个。

如果题目要求“第一个 ≥ x”或“最后一个 ≤ x”，需要设计对应的边界二分。

07为什么是 O(log n)？

每次都把剩余范围大约减半：

1024 个元素大约只需要 10 次“减半”就能缩到 1 个范围。