二分查找算法详解:核心原理与实战应用
二分查找是一种经典的高效查询方法,其核心思想是通过不断将查找范围缩小为一半,从而大幅降低时间复杂度。
在一个有序数组中,若采用遍历方式查找目标元素,时间复杂度为 O(n)。而使用二分算法,每次从待遍历数组的中心位置开始判断:
- 若当前值小于目标值,说明目标在右区间,更新左边界;
- 若当前值大于目标值,说明目标在左区间,更新右边界。

最坏情况下只需遍历 log(n) 次。这意味着在 100 万个数中查找目标元素最多只需要 20 次,效率提升显著。
一、算法细节与陷阱
二分算法的本质不难理解,但在具体落地时,细节处理往往决定了代码的正确性。
1. 左右临界点更新
我们需要 left 和 right 指针标记区间边界,每次迭代后需根据比较结果更新。
- 目标元素不重复:直接移动边界即可,例如
right = mid - 1。 - 连续序列的左端点:若
cur >= 目标值,cur可能是结果,需保留当前位置,故right = cur;否则left = mid + 1。 - 连续序列的右端点:若
cur <= 目标值,cur可能是结果,故left = cur;否则right = mid - 1。

2. 中点选择策略
当区间长度为偶数时,中点有两个可选位置(左中点或右中点)。
- 基础查找:不影响结果,任选其一。
- 查找左端点:需选 左中点。若选右中点且
mid >= target,可能导致right不变,陷入死循环。 - 查找右端点:需选 右中点。同理可避免死循环。

3. 循环条件设计
是 left < right 还是 left <= right?这取决于相遇后是否还需判断。
- 基础查找:相遇后仍需判断该位置是否为目标值,故用
left <= right。


