前言

二分搜索

不重复升序数组查询元素

最经典的二分搜索是在一个 有序、不重复 的数组中，查询某个元素 x 的索引。

public int binary(int[] nums, int x) {
    int l = 0, r = nums.length - 1, m;
    // 这里为什么是 <= 而不是 <
    // 因为 [l, r] 是一个左闭右闭的区间，如果没有 = 则会漏解
    while (l <= r) {
        m = l + (r - l) / 2;
        if (nums[m] < x) {
            l = m + 1;
        } else if (nums[m] > x) {
            r = m - 1;
        } else {
            return m;
        }
    }
    return -1;
}

注意求中点的写法：

m = l + r >> 1;
m = (l + r) / 2;
m = l + (r - l) / 2;
m = l + ((r - l) >> 1);

这四种写法都是 ok 的

• 在正整数中，除 2 可以使用右移 1 位来代替。
• 第 3、4 种写法可以防止溢出，对于 int 型来说，要想发生溢出，数据规模至少在 10 亿（10^9），所以一般第 1 种写法足以应对大部分场景。

重复正序数组查询 ≥ x 的最左位置

在一个重复正序数组中，查询 ≥ x 的最右位置是无意义的，只需要看数组最后一个元素是否满足条件即可。

在一个重复正序数组中，查询 ≥ x 的最左位置，使用变量 ans 记录每一次向左二分时的 m 的位置，只要 nums[m] ≥ x，那么继续向左二分。

public int binary(int[] nums, int x) {
    int l = 0, r = nums.length - 1, m;
    int ans = -1;
    while (l <= r) {
        m = l + r >> 1;
        if (nums[m] >= x) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

重复正序数组查询 ≤ x 的最右位置

在一个重复正序数组中，查询 ≤ x 的最左位置是无意义的，只需要看数组第一个元素是否满足条件即可。

在一个重复正序数组中，查询 ≤ x 的最右位置，使用变量 ans 记录每一次向右二分时的 m 的位置，只要 nums[m] ≤ x，那么继续向右二分。

public int binary(int[] nums, int x) {
    int l = 0, r = nums.length - 1, m;
    int ans = -1;
    while (l <= r) {
        m = l + r >> 1;
        if (nums[m] <= x) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

更多题目

有关二分搜索，二分答案类题目是一类型题目，给了我们解决问题从答案入手的思路。

另外，在 LeetCode 上还有一组旋转数组类题目。

参考：二分搜索