LeetCode 二分查找

基础 - 704 二分查找

传送门

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

这可以说是非常基础的题目了。但也是有可以总结的东西的。

二分查找实际写起来，最讨厌的就是边界情况：while 中是 l < r 还是 l <= r ? 要想彻底解决这个问题，得对自己变量的含义有一个明确的定义。

比如我的解法（java）：

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1; // 在 [L,R] 闭区间查找
        while (l <= r) {
            int mid = l + (r - l) / 2; // prevent overflow
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

我把要执行搜索的区间定义为 [L,R] 闭区间，因此当 L==R 时表示只搜索 L 这一个位置，是有意义的。因此 while 中就要包含等于的情况，否则就可能漏掉一个位置。同理，第 7 行需要把 r 更新为 mid-1，这样下一轮的搜索区间才不会和本轮有重叠。

相反，如果把搜索区间定义为 [L,R) 左闭右开区间，当 L==R 时就没有意义了，因为此时不会有任何一个位置在这个区间里，因此 while 中只需要 L<R 就好。自然，第 7 行需要把 r 更新为 mid，因为右侧是开区间，令 r=mid，实际执行搜索的的区间正好是 [L, mid-1]。注意，此时第 9 行依然保持 l = mid + 1，因为左侧是闭区间，需要把 mid 排除掉。

除此之外，还有考虑数值溢出问题。 int + int 不见得还在 int 范围里。因此计算 mid 的时候用了一个小技巧（见代码）。

35 - 搜索插入位置

传送门

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

这道题的关键是如何得出需要插入的位置。

一开始我想在 mid 上做文章，但发现 mid 不见得是最后插入的位置，例如：

[ 1, 3, 5, 7]  2

最后一次搜索时 mid=0，显然，我们应该插在 1 位置。而另一组数据：

[ 1, 3, 5, 7]  0

最后一次搜索时依然是 mid=0，但这次恰好插在 0 位置。 当然，我们可以对 nums[mid] 与 target 进一步判断，不过实际上有一个更好的方案。

既然分析的是需要插入数据的情况，我们可以确定 target 肯定不在数组里。具体需要插入的地方，只有三种情况：

1. 插到最左边。
2. 插到中间。
3. 插到最右边。

对于中间的情况，最终的搜索范围一定会收缩到 [i, i+1]，显然 (i+i+1)/2=i，因此总是先检查左侧的数据。而左侧的数据必定偏小（相对于 target），根据算法，导致了 L=R=i+1。然后检查右边，其必定偏大，于是 R = mid-1 = i。则 R+1 就是需要插入的位置。

对于插到左侧的情况，最后搜索范围必定收缩到 [0, 0]，其值偏大。于是 R=0-1=-1，那么 R+1 也正好是答案。

最后对于插到最右侧的情况，最后搜索范围必定是 [n, n] （n=len(num)-1），其值偏小，那么 R 不更新，R+1 还是答案。

因此，答案是只需返回 R+1，代码如下：

class Solution {
    public int searchInsert(int[] nums, int target) {
      
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2; // prevent overflow
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r + 1;
    }
}

34 - 元素位置区间

传送门

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

我们知道要使用二分查找，数据需要满足两个条件：

1. 有序。
2. 没有重复元素。

若有重复元素，其实也是可以找到的，但只能找到其中的一个，并且位置无法保证。

这个题是针对二分查找的局限性出的，我们就需要补充一点算法来弥补它。这里提供两个算法：

1. 分别向前后遍历。显而易见的方式，效率略低，主要取决于元素重复的个数。
2. 找到元素时不停止二分查找，而是假装没找到，排除当前位置元素继续查找。 根据二分算法的原理，这个方式可以跳过多个连续的重复元素，但在元素重复很少的时候略微费时。

第二个总体高效一些，代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = getBorder(nums, target, true);
        int r = getBorder(nums, target, false);
        return new int[]{l, r};
    }

    private int getBorder(int[] nums, int target, boolean leftEnd) {
        int result = -1;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                result = mid;
                if (leftEnd)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }
        return result;
    }
}

PS：这个答案可以进一步优化。这里第一次找到元素的过程实际上执行了两边。因此我们可以先用标准的二分查找找到一个位置，把原始数组分为左右两部分，分别进行修改后的二分查找从而得出边界。