小虾米

2023-11-02 2023-11-03 约 3500 字预计阅读 7 分钟 - 次阅读

警告

本文最后更新于 2023-11-03，文中内容可能已过时。

二分查找

二分查找的前提条件：

有序数组
无重复元素

二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

在写数组的题目的时候，千万不要花太多精力在考虑下标的奇偶性和除以 2 以后的奇偶性上，直接将其放到一个范围考虑即可。只要是在一个范围里面，那么总是不会漏掉数据的，

左闭右闭区间写法，即 $[left , right]$ ，这也是推荐的写法

C++版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


//版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right =nums.size()- 1; // 定义 target 在左闭右闭的区间里，[left,right]
        while (left <= right){ //当 left == right，区间 [left,right] 依然有效，所以用 <=
            int middle= left+((right - left)/2); //防止溢出 等同于 (left + right)/2
            if (nums[middle] > target) {
                right =middle - 1;// target 在左区间，所以 [left,middle-1]
            } else if (nums[middle] < target) {
                left=middle+1; // target 在右区间，所以 [middle+1,right]
            } else { // nums[middle] == target
                return middle; //数组中找到目标值，直接返回下标
            }
        }
        //未找到目标值
        return -1;
    }
};

Java 版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public static int binarySearch0(int[] nums, int target) {
    // 避免当 target 小于 nums[0] nums[nums.length - 1] 时多次循环运算
    if (target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > target) {
            //二分法，快就快在这里，一次循环，就把范围缩小一半
            right = middle - 1;
        } else if (nums[middle] < target) {
            //二分法，快就快在这里，一次循环，就把范围缩小一半
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

注意，在这个写法中，对边界的处理的统一，体现在，while的判断条件是包含左右两个边界的，left可以等于right，在判断中，移动left或right的时候，是直接从middle+1或者middle-1开始，如果左开的话，那么应该是从 middle 开始，因为不包含左边界，循环的时候，会从middle+1开始遍历，这就是写法要和定义统一的体现。

具体看另一种写法：

左闭右开即$[left, right)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

二分法快在哪里？二分法快就快在，经过一次循环就可以把搜索范围缩小一半，所有的精髓，都在 right = middle - 1;和left = middle + 1; 上

二分法是查找有序数组最快的方式。

有序数组，就可以用二分查找，而且有的时候，题目提示使用 $\log(n)$ 的时间复杂度，基本上可以认为就是要求你用二分法查找。

35.搜索插入位置

题目链接

直接套用二分法，很简单

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public int searchInsert0(int[] nums, int target) {
    int start = 0, end = nums.length-1;
    while (start <= end) {
        int mid = (end - start) / 2 + start;
        if (target <= nums[mid]) {
            end = mid - 1;
        }else{
            start= mid + 1;
        }
    }
    return start;
}

34.在排序数组中查找元素的第一个和最后一个位置

题目链接

一开始只能想到双指针逼近法，但是这个方法的时间复杂度为$O(n)$，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


public int[] searchRange(int[] nums, int target) {
    if( nums.length ==0 || target < nums[0] || target > nums[nums.length-1]){
        return new int[]{-1,-1};
    }

    int outerleft = 0;
    int outerright = nums.length-1;
    while(outerleft<=outerright){
        if(nums[outerleft]<target){
            outerleft++;
        }
        if(nums[outerright]>target){
            outerright--;
        }
        if(nums[outerright]==target && nums[outerleft] ==target){
            return new int[]{outerleft,outerright};
        }
        if(outerleft==outerright){
            if(nums[outerright]==target){
                return new int[]{outerleft,outerright};
            }else{
                return  new int[]{-1,-1};
            }
        }
    }
    return  new int[]{-1,-1};
}

下面是 $O(\log n)$的写法

先用二分法求左边界，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static int leftBorder(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    int leftBorder = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] < target) {
            left = middle + 1;
        }else{
            //从右侧逼近
            right = middle - 1;
            if (nums[middle] == target) {
                leftBorder = middle;
            }
        }
    }
    return leftBorder;

}

然后求右边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static int rightBorder(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    int rightBorder = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > target) {
            right = middle - 1;
        }else{
            //从左侧逼近
            left = middle + 1;
            if (nums[middle] == target) {
                rightBorder = middle;
            }
        }
    }
    return rightBorder;

}

变幻一下leftBorder核心部分的写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public static int leftBorder2(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    int leftBorder = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] >= target){
            right = middle - 1;
            if (nums[middle] == target) {
                leftBorder = middle;
            }
        }else{
            left = middle + 1;
        }
    }
    return leftBorder;

}

你会发现跟 rightBorder 的差别就只有在 nums[middle] == target 的时候，如果是右边界，那么 nums[middle] == target 的时候，除了 rightBorder = middle; 还有 left = middle + 1; 如果是左边界，那么nums[middle] == target 的时候，除了 leftBorder = middle; 还有 right = middle - 1; 看明白了吗？nums[middle] == target 的时候改的是左边界还是右边界，决定了最后得出的是左边界还是右边界。

合并！！！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


/**
 * 你会发现跟 rightBorder 的差别就只有在 nums[middle] == target 的时候，
 * 如果是右边界，那么 nums[middle] == target 的时候，除了 rightBorder = middle; 还有 left = middle + 1;
 * 如果是左边界，那么 nums[middle] == target 的时候，除了 leftBorder = middle; 还有 right = middle - 1;
 * 看明白了吗？nums[middle] == target  的时候改的是左边界还是右边界，决定了最后得出的是左边界还是右边界
 * 合并！！！
 * 这是最完美的方法，卡哥的方法没有这个好
 */
public static int border(int[] nums,int target,boolean leftFlag){
    if(nums.length ==0 || target<nums[0]|| target > nums[nums.length-1]){
        return -1;
    }
    int index = -1;
    int left  = 0;
    int right = nums.length-1;
    while(left<=right){
        int middle =  left + (right - left)/2;
        if(nums[middle] > target){
            right = middle -1;
        }else if(nums[middle]<target){
            left = left+1;
        }else{
            index = middle;
            if(leftFlag){
                right = middle-1;
            }else{
                left = middle +1;
            }
        }
    }
    return index;
}

这就是最终答案，找左边界的复杂度是$O(\log n)$，右边界的复杂度也是$O(\log n)$，$2 \times O(\log n)$ ，最后复杂度为$O(\log n)$。

跟常规的二分法相比，重点在于nums[middle] = target的时候，不直接饭回，而是继续循环，直到 left > right的时候跳出循环，这样相当于已经遍历了整个数组了。

69.x 的平方根

题目链接

题目不难，把寻找平方根，看成是在 $f(n) = n^2 ,n \in (0-x]$ ，我们要在$(0-x]$这个正序数组中寻找x对应的n，直接用二分法找。

有三点需要注意：

把0排除
这里不能直接写 middle * middle > x 结果过大，会造成溢出，用 middle > x/middle，注意，用 middle == x/middle 判断平方根是不准确的，判断是平方根还要判断余数x%middle，但是题目中是求平方根的整数部分，x/middle正好就是，所以这里可以这么用。367题就不行
middle == x/middle的时候可直接返回下标，毫无疑问的最接近的数，除此之外，要判断最靠近x的整数，需要满足条件：middle* middle < x && (middle+1)* (middle+1) > x ，我们可以记录右边界（相当于(middle+1)* (middle+1) > x的时候的middle，跳出循环之前的最后一次判断的时候，left==right，left == middle这个值，而且middle* middle < x，刚好满足条件），所以我们只需要一直记录右边界，然后在跳出循环的时候返回右边界即可，反过来其实也可以，不过那就不是记录left，而是记录middle，如果我们要找的是大于x平方根的最小整数，那就可以直接返回left。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


/**
 * 把寻找平方根，看成是在 f(n) = n^2  n 属于 0-x 这个正序数组中寻找 x 对应的 n，直接用二分法找。
 * @param x
 * @return
 */
public static int mySqrt(int x) {
    // 先把 0 排除，不然当输入 0 的时候，直接走二分法会出现 0 除以 0 的情况
    if (x == 0) {
        return 0;
    }
    int result = 0;
    int left = 1;
    int right = x;
    while(left <= right){
        int middle = left + (right - left)/2;
        //这里不能直接写 middle*middle  > x 结果过大，会造成溢出，
        // 比如 middle = 1073697800，middle*middle = 1938112576，甚至变成复数都有可能
        if(middle > x/middle ){
            right = middle -1 ;
            // middle -1 就是我们要求的整数：小于 x 平方根的最大整数
            result = right;
        }else if (middle < x/middle ){
            left = middle+1;
        }else {
            return middle;
        }
    }
    return result;
}

另一种方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static int mySqrt0(int x) {
    // 先把 0 排除，不然当输入 0 的时候，直接走二分法会出现 0 除以 0 的情况
    if (x == 0) {
        return 0;
    }
    int result = 0;
    int left = 1;
    int right = x;
    while(left <= right){
        int middle = left + (right - left)/2;
        //这里不能直接写 middle*middle  > x 结果过大，会造成溢出，
        // 比如 middle = 1073697800，middle*middle = 1938112576，甚至变成复数都有可能
        if(middle > x/middle ){
            right = middle -1 ;
        }else if (middle < x/middle ){
            left = middle+1;
            //我们要记录的是 middle，如果求大于 x 平方根的最小整数，那就可以返回 left
            result = middle;
        }else {
            return middle;
        }
    }
    return result;
}

只要是有序数组，就用得上二分法

367.有效的完全平方数

题目链接

什么是完全平方数？如果一个正整数 a 是某一个整数 b 的平方，那麼這个正整数 a 叫做完全平方数。0也可称为完全平方数。

跟69题几乎一样，这里是求num的正整数平方根，如果存在，就是完全平方数，如果不存在，那就不是

这个题要注意三点：

首先排除0
在判断平方相等的时候，要同时判断除数和余数，middle == num/middle 而且 num % middle == 0，middle才是其平方根

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


public static int sqrt(int num){
    if(num ==1){
        return 1;
    }
    int index = -1;
    int left = 2;
    int right = num-1;
    while(left <= right){
        int middle = left + (right - left)/2 ;
        if(middle > num/middle){
            right = middle - 1;
        }else if(middle < num/middle){
            left = middle + 1 ;
        }else{
            // middle == num/middle 的时候对比余数
            // 代码这么写不是最简洁的，但是是最好理解的
            if (num % middle == 0) {
                return middle;
            }else{
                //余数不为 0，说明还是大了
                right = middle - 1;
            }
        }
    }
    return index;
}

704.二分查找

题目链接

TODO