查找

想象你在一个乱序的书架上找一本《算法导论》。最直接的办法是从头开始一本一本看过去，直到找到目标——这就是线性查找。它很简单，但如果书架上有1000本书，最坏情况下你要翻1000次。当数据量很大时，这种“逐个检查”的方式效率很低。

如果书架上的书是按书名字典序排好的，你还会从头翻吗？不会。你会先看中间那本：如果它比《算法导论》靠后，就说明目标在前半堆；否则在后半堆。这样每查一次，搜索范围就缩小一半。这就是二分查找的核心思想：每次将查找区间对半分割，只保留可能包含目标的那一半。

二分查找之所以能“砍一半”，是因为我们利用了有序性来推断目标在哪一侧。如果数据无序，中间值无法告诉我们任何方向信息，二分查找就失效了。所以，使用二分查找前，数据必须已经排好序（升序或降序）。

实现二分查找时，我们用两个指针 l 和 r 表示当前搜索区间的左右边界（闭区间）。每次取中间位置 mid = (l + r) / 2（整数除法），比较 arr[mid] 与目标值：

• 如果相等，找到目标。
• 如果 arr[mid] < target，说明目标在右半侧，令 l = mid + 1。
• 如果 arr[mid] > target，说明目标在左半侧，令 r = mid - 1。

循环条件为 l <= r，保证区间有效。注意 mid ± 1 是为了避免死循环，因为每次排除 mid 位置。

二分查找的时间复杂度是 O(log n)，意味着数据量翻倍，比较次数只增加1次。它适用于静态有序数据的频繁查找（如数据库索引、字典查词）。但若数据频繁插入删除，维护有序性的成本可能超过查找收益，此时需权衡。