Java 二分查找：有序数组的 O(log n) 神器

学会这一招，10 亿数据也能在 30 次比较内找到目标

引言

二分查找（Binary Search）是最简单也最容易被写错的算法。

原理一句话：每次砍一半，砍到找到为止。10 亿个有序数据，最多 30 次比较就能定位目标——这就是 O(log n) 的威力。

但实际写代码时，边界条件 + 整数溢出两个坑能绊倒一半程序员。

1. 核心思想

前提：数组必须有序。

步骤：

1. 维护左右指针 left、right
2. 取中点 mid = (left + right) / 2
3. 比较 arr[mid] 与目标值：
   • 相等 → 找到，返回 mid
   • arr[mid] < target → 目标在右半边，left = mid + 1
   • arr[mid] > target → 目标在左半边，right = mid - 1
4. left > right → 没找到，返回 -1

时间复杂度：O(log n)。10 亿数据最多 30 次比较（2³⁰ ≈ 10 亿）。

2. Java 实现

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
        int target = 23;
        int index = binarySearch(sortedArray, target);
        if (index != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为: " + index);
        } else {
            System.out.println("元素 " + target + " 不存在于数组中");
        }
    }
}

运行结果：元素 23 在数组中的索引为: 5

3. 三个关键细节

细节 1：循环条件用 left <= right

不是 left < right。等于的情况是 left == right == mid，数组里还剩一个元素没检查，必须检查。

细节 2：中点计算用 left + (right - left) / 2

不是 (left + right) / 2——后者在 left + right > Integer.MAX_VALUE 时会整数溢出变成负数。

细节 3：边界更新用 mid ± 1，不是 mid

left = mid + 1 和 right = mid - 1——因为 arr[mid] 已经比较过，下次不再纳入范围。

如果写成 left = mid 或 right = mid，可能死循环（当 left + 1 == right 时）。

4. 适用场景与限制

适用：

• 静态有序数组：数据不变，预先排好序
• 查找远多于插入删除：查询 O(log n) 但插入删除 O(n)（要搬移元素）
• 内存连续：需要随机访问 arr[mid]

不适用：

• 无序数组（要先排序，O(n log n)，得不偿失）
• 频繁插入删除（用红黑树/AVL 树，O(log n) 全程稳定）
• 链表（无法随机访问，要用专门的链表二分变体）

JDK 里 Arrays.binarySearch() 就是这套实现，生产环境直接用，不要自己写。

5. 面试常见变形

变形	关键调整
找第一个等于 target	arr[mid] >= target 时 right = mid
找最后一个等于 target	arr[mid] <= target 时 left = mid
找第一个大于等于 target	同上模式
旋转排序数组搜索	先判断哪半边有序，再决定砍哪边

核心套路：先写对基础版，再根据”找第一个/最后一个”调整边界。

总结

二分查找 = 每次砍一半。有序数组的 O(log n) 神器，10 亿数据 30 次比较。

三个易错点：

• 循环条件 left <= right（带等号）
• 中点计算防溢出
• 边界更新 mid ± 1（不是 mid）

下一步：用同样的思路刷 LeetCode 704（二分查找基础）、35（搜索插入位置）、34（在排序数组中查找元素的第一个和最后一个位置）——这三道题搞懂，二分就稳了。

---