简单又不简单的二分法

二分法的思路比较简单,但往往不容易写对,比如要不要加等号、死循环等问题。实际上,二分法就是一个逐步缩小范围的过程,每次缩小一半。

经典应用

最经典的二分法的应用是:一个有序数组arr(例如升序),数组元素不同,从数组中找数target的索引,如果不存在返回-1。代码比较简单:

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + right >> 1;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

如图所示。首先,由于不知道target在哪,就取全范围,也就是[0, arr.length - 1],target如果能找到则索引必然位于这个范围。然后取mid,发现arr[mid] < target,这说明target的索引必然位于[mid + 1, right]范围,所以调整left = mid + 1,以此类推其它的情形。

循环条件

为什么这里的while循环条件里 left <= right 要取等号呢?如果不取等号,假设我们的target变为2,经过第一次循环后,left = 0, right = 1, 然后计算mid = 0, 接着就会调整left = 1,于是退出while循环,此时返回-1,但实际上此时left = right = 1已经是target所处的位置了。因此,如果while循环条件改为left < right,在循环结束时还需要检查下arr[mid]是否等于target。

推广应用

当然,上面的例子比较简单,更一般的情况是,数组arr并非严格单调(例如单调不减),从数组中找数target第一次和最后一次出现的位置。这个是LeetCode上挺经典的一道题:Find First and Last Position of Element in Sorted Array - LeetCode

如图所示,阴影部分为数组中值为target的部分。

问题分析

假设我们的目标是找target第一次出现的位置,考虑mid位于图中1、2、3位置时的情况:

1:假如mid位于1,很显然,我们能断定target第一次出现的位置位于[mid + 1, right];
2:假如mid位于2,为了找target第一次出现的位置,我们需要将right移至mid的位置。因为2处可能正好就是target第一次出现的位置,所以不能把right移至mid - 1。
3:假如mid位于3,很显然,我们能断定target第一次出现的位置位于[left, mid - 1]

对于以上的情况2、3,由于都是移动right,不妨将其合并,也就是当arr[mid] >= target时,right = mid。虽然这样做对于情况3少移了一格,但影响不大,且会让代码更为精简。

假设我们的目标是找target最后一次出现的位置,考虑mid位于图中1、2、3位置时的情况:

1:假如mid位于1,很显然,我们能断定target最后一次出现的位置位于[mid + 1, right]
2:假如mid位于2,为了找target最后一次出现的位置,我们需要将left移至mid的位置。因为2处可能正好就是target最后一次出现的位置,所以不能把left移至mid + 1。
3:假如mid位于3,很显然,我们能断定target最后一次出现的位置位于[left, mid - 1]

同样的,对于以上的情况1、2,由于都是移动left,不妨将其合并,也就是当arr[mid] <= target时,left = mid。

mid偏向

值得注意的是,mid在计算时偏向left,例如left = 0, right = 1时,mid = 0,此时mid与left相等,如果继续进行left = mid的赋值,将导致死循环。解决此问题的方法是,在计算mid时先加1:

int mid = left + right + 1 >> 1;

本题参考代码:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1, -1};
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if (nums[left] != target) return new int[]{-1, -1};
        int st = left;
        left = st; right = nums.length - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return new int[]{st, left};
    }
}

速记版:

lower_bound: mid = left + right >> 1, arr[mid] >= target, right = mid
upper_bound: mid = left + right + 1 >> 1, arr[mid] <= target, left = mid

拓展思考

关于计算mid时溢出的问题

实际上,如果写成

int mid = left + (right - left) / 2

仍然有溢出问题,例如left = INT_MIN, right = INT_MAX。可以将left和right强制转为长整型以解决溢出问题。

二分法好题

算法

上一篇 快速幂取余算法
下一篇 解决leetcode-publisher的代码中文乱码BUG

添加新评论

*
*