二分查找

二分查找（Binary Search）是一种在 有序数组 中查找某一特定元素的查找算法。其时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。

核心思想

每次将搜索区间缩小一半：

1. 找出中间元素 mid = (left + right) / 2 (建议使用 left + (right - left) / 2 避免溢出)。
2. 将 mid 与目标值 target 比较。
3. 若 target < mid，去左半部分查找；若 target > mid，去右半部分查找。

基本模板

public int search(int[] arr, int target) {
    int left = 0, 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;
}

查找边界：lower_bound 与 upper_bound

当数组中有重复元素，需要找到第一个或最后一个 target 时，基本二分需要调整。

1. 查找第一个等于 target 的位置 (lower_bound)

public int findFirst(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            res = mid;
            right = mid - 1;  // 继续向左半部查找
        } else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return res;
}

2. 查找最后一个等于 target 的位置 (upper_bound)

同理，若 arr[mid] == target，则 left = mid + 1，继续向右半部查找。

二分答案 Binary Search Answer

这是一种非常重要的算法技巧：如果直接求最优解很难，但容易验证某个方案是否可行且满足单调性，可以使用二分法在解的可能范围内搜索最优解。

适用场景

1. “求最大值的最小值” 或 “求最小值的最大值”。
2. 给定范围 [left, right]，且满足单调性。

经典实例：爱吃香蕉的珂珂 (LeetCode 875)

给定 $n$ 堆香蕉，每堆有若干个。珂珂需要在 $h$ 小时内吃完所有。选择最小的吃速 $k$。

• 范围：$k$ 最小为 1，最大为香蕉堆中最大的那一堆。
• 单调性：由于吃速越快，耗时越少，因此满足单调性。
• 验证：二分 $k$，调用函数 canEatAll(speed, h) 验证。

练习

1. LeetCode 704：二分查找
2. LeetCode 33：搜索旋转排序数组
3. LeetCode 34：在排序数组中查找元素的第一个和最后一个位置
4. LeetCode 35：搜索插入位置
5. LeetCode 69：x 的平方根 (数值二分)
6. LeetCode 875：爱吃香蕉的珂珂 (二分答案)
7. LeetCode 410：分割数组的最大值 (二分答案)