二分查找汇总

@Yi-Xing 2021-02-15 0 评论 0 浏览

LeetCode 算法

二分查找

二分查找通过不断缩小搜索区间的范围，直到找到目标元素或者没有找到目标元素。不断缩小搜索区间是一种减而治之的思想，也称为减治思想。二分查找算法的两种思路：在循环体中查找元素；在循环体中排除目标元素一定不存在的区间。

1、中间数

在二分查找中，最初的取中间数的代码 int mid = (left + right) / 2;，严格意义上，这段代码存在 bug，因为 left + right 可能存在溢出。可以写成 int mid = left + (right - left) / 2;。你可能还见过 int mid = (left + right) >> 1; 其实它和 int mid = (left + right) / 2; 的结果是相同的，也存在溢出问题。

在 Java 中可以使用 int mid = (left + right) >>> 1; 这种写法，>>> 是无符号右移，在 left + right 发生整型溢出的时候，右移一位由于高位补 0。

中间数的向上取整和向下取整

在上面计算 mid 的公式，都是向下取整，因为 / 2 这个除号表示的含义是下取整。如果想向上取整使用 int mid = left + (right - left + 1) / 2;，两种取整方式需要区别对待，具体下文介绍。

2、二分查找的最基本问题

最基本的二分查找是力扣 704 题，在循环体中查找元素。在一个有序数组里查找目标元素的下标，目标元素不存在，返回 -1。如果中间的那个元素正好等于目标元素，我们就可以直接返回这个元素的下标；否则我们就需要在中间这个元素的左边或者右边继续查找。

迭代写法：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        // 目标元素可能存在在区间 [left, right]
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 目标元素可能存在在区间 [mid + 1, right]
                left = mid + 1;
            } else {
                // 目标元素可能存在在区间 [left, mid - 1]
                right = mid - 1;
            }
        }
        return -1;
    }
}

递归写法：

class Solution {
    public int search(int[] nums, int target) {
        return search(nums, 0, nums.length - 1, target);
    }

    public int search(int[] nums, int left,int right, int target) {
        if (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                return search(nums, mid + 1, right, target);
            } else {
                return search(nums, left,  mid - 1, target);
            }
        }
        return -1;
    }
}

3、二分排除法

二分排除法的思路：排除了所有错误的答案，当 left == right 时，表示区间里只剩下一个元素的时候，有可能这个元素就是我们要找的那个元素。在退出循环以后，进行单独做一次判断。

如果这个二分查找的问题比较简单，在输入数组里不同元素的个数只有 1 个，使用上面方法，在循环体内查找这个元素；
如果这个二分查找的问题比较复杂，要你找一个可能在数组里不存在，或者是找边界这样的问题，使用该方法，在循环体内排除一定不存在目标元素的区间会更简单一些。

在力扣 704 题中，我们要找等于 target 的元素，当前 mid 不等于 target 时，则缩小区间。在循环体里排除一定不存在目标元素的区间，向下取整。

class Solution {

    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 目标元素可能存在在区间 [left, right]
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间是 [left, mid]
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}

向上取整。

class Solution {

    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                // 下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid, right]
                left = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}

向下取整，预留两个数。这种思路循环可以继续的条件是 while (left + 1 < right) ，在待搜索区间剩下两个元素的时候，退出循环，所以它不需要考虑死循环的问题；

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // 目标元素可能存在在区间 [left, right]
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        return -1;
    }
}

4、中间数取整方式

在排除法中，有时候使用 int mid = left + (right - left) / 2;，有时候使用 int mid = left + (right - left + 1) / 2;。那何时使用向下取整，何时使用向上取整呢？这个二分法的思路根据中间数的值把区间分为两个部分：

一定不存在目标元素的部分；
可能存在目标元素的部分。

中间数的位置有两种情况。

情况一：mid 被分到左边区间

分区被分为两部分：[left, mid] 与 [mid + 1, right]，对应设置边界的代码为 right = mid 和 left = mid + 1;

情况二：mid 被分到右边区间

分区被分为两部分： [left, mid - 1] 与 [mid, right]，对应设置边界的代码为 right = mid - 1 和 left = mid。注意：这种情况下，当搜索区间里只剩下两个元素的时候，一定要将取中间数改成上取整，也就是在括号里加 1。

因为 [left, right] 区间里只剩下两个元素的时候，如果是取中间数 mid 是下取整，一旦进入 left = mid 这个分支，区间就不会再缩小。

边界设置的两种写法：

right = mid 和left = mid + 1 和int mid = left + (right - left) / 2; 一定是配对出现的；
right = mid - 1 和left = mid 和int mid = left + (right - left + 1) / 2; 一定是配对出现的。

5、练习

1）在排序数组中查找数字 I

自己的想法

方法一：二分查找

使用二分查找找到该数，然后向左右扩散寻找边界。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.3 MB, 在所有 Java 提交中击败了63.16%的用户

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        // 目标元素可能存在在区间 [left, right]
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                int count = 1;
                for (int i = mid - 1; i >= 0 && nums[i] == target; i--) {
                    count++;
                }
                for (int i = mid + 1; i < nums.length && nums[i] == target; i++) {
                    count++;
                }
                // 向左和右扩散查找
                return count;
            } else if (nums[mid] < target) {
                // 目标元素可能存在在区间 [mid + 1, right]
                left = mid + 1;
            } else {
                // 目标元素可能存在在区间 [left, mid - 1]
                right = mid - 1;
            }
        }
        return 0;
    }
}

看题解后

方法二：左右边界下标

如果 target 存在于数组中，则寻找 target 在数组中的左右边界，相减后加一，就是该数在数组的个数。

public class Solution {

    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        // 寻找该数在数组的左边界
        int left = getLeft(nums, target);
        // 不存在则返回 0
        if (left == -1) {
            return 0;
        }
        // 寻找该数在数组的右边界
        int right = getRight(nums, target);
        return right - left + 1;
    }

    private int getLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 注意这样写，可以从左边收缩待搜索区间的范围，进而找到第一次出现的位置
            if (nums[mid] < target) {
                // mid 以及 mid 左边都不是，下一轮搜索区间在 [mid + 1, right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    private int getRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意这样写，可以从右边收缩待搜索区间的范围，进而找到最后一次出现的位置
            if (nums[mid] > target) {
                // mid 以及 mid 右边都不是，下一轮搜索区间在 [left, mid - 1]
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

方法三：左右边界

另一种求左右边界的方法。该方法和上面方法求的边界不同。

方法二：适用于查找存在于数组中的数的边界，返回的是该数在数组中的边界下标（包含边界）。数的个数为：right - left + 1。
方法三：返回的是该数在数组中的位置边界（不包含边界）。数的个数为：right - left - 1。

例如：int[] num = {1, 2, 2}; 找 2；int[] num = {1, 3}; 找 2.

方法二：left = 1, right = 2；left = 1, right = 0（无意义，不适应查找不存在的数，应该进行判断返回 -1）。
方法三：left = 0, right = 3；left = 0，right = 1。

class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int right = getRight(nums, target);
        // 若数组中无 target ，则提前返回
        if (right == -1) {
            return 0;
        }
        // 搜索左边界 left
        int left = getLeft(nums, target);
        return right - left - 1;
    }

    public int getRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            // 左右边界的区别，相等时，排除哪个分区
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 提高效率，若数组中无 target ，则提前返回。求边界时，不需要该判断
        if (right >= 0 && nums[right] != target) {
            return -1;
        }
        return left;
    }

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

方法四：右边界

分别二分查找 target 和 target - 1 的右边界，将两结果相减并返回即可。

class Solution {
    public int search(int[] nums, int target) {
       return getRight(nums, target) - getRight(nums, target - 1);
    }

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

2）搜索插入位置

自己的想法

方法一：二分查找

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了12.85%的用户

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        // 目标元素可能存在在区间 [left, right]
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 目标元素可能存在在区间 [mid + 1, right]
                left = mid + 1;
            } else {
                // 目标元素可能存在在区间 [left, mid - 1]
                right = mid - 1;
            }
        }
        // right + 1
        return left;
    }
}

方法二：使用 API

class Solution {
    public int searchInsert(int[] nums, int target) {
        int tmp = Arrays.binarySearch(nums, target);
        if (tmp < 0) {
            return -(tmp + 1);
        }
        return tmp;
    }
}

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

自己的想法

方法一：二分查找

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了29.26%的用户

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int right = getRight(nums, target);
        if (nums.length == 0 || nums[right] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{getLeft(nums, target), right};
    }

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

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

4）寻找旋转排序数组中的最小值

自己的想法

方法一：排序性质

因为原数组是升序的，正常情况下 nums[i - 1] <= nums[i]，所以如果 nums[i - 1] > nums[i]，则 nums[i] 肯定是原数组的开头，即最小值。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了13.10%的用户

class Solution {
    public int findMin(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > nums[i]) {
                return nums[i]; 
            }
        }
        return nums[0];
    }
}

看题解后

方法二：二分查找

使用二分查找，根据中间数进行判断，不断收缩左边界或右边界。左、中、右三个位置的值相比较，有以下几种情况：

         右 
     中	   
 左	   
-----------
 左   
         右
     中
-----------
     中  
 左 
         右
-----------

我们可以找到一个变化点，这个点有如下特点：

所有变化点左侧元素 > 数组第一个元素；
所有变化点右侧元素 < 数组第一个元素。

判断变化点的位置：

找到数组的中间元素 mid；
如果中间元素 > 数组第一个元素，则变化点在 mid 右边；
如果中间元素 < 数组第一个元素，则变化点在 mid 左边。

验证是否找到变化点：

当我们找到变化点时停止搜索，当以下条件满足任意一个即可：
nums[mid] > nums[mid + 1]，因此 mid+1 是最小值；
nums[mid - 1] > nums[mid]，因此 mid 是最小值。

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[0] <= nums[right]) {
            return nums[0];
        }
        while (true) {
            int mid = (left + right) / 2;
            // 当中间的数大于右边的数，则 mid + 1 就是旋转点
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            // 当中间的数小于左边的数，则 mid 就是旋转点
            if (nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            // 根据第一个数，进行移动
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
}

判断右边的数。我们把数组从中间分成两个数组（两个数组都包含中间数），不难发现最小数永远在无序数组中。

如果中间的数小于等于右边的数，表示右边的数是有序的，则说明最小数的下标为 <= mid
如果中间的数大于右边的数，表示左边的数是有序的，则说明最小数的下标为 > mid

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

判断左边的数。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[left]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return Math.min(nums[0], Math.min(nums[left], nums[right]));
    }
}

判断头部的数。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return Math.min(nums[0], nums[left]);
    }
}

判断尾部的数。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= nums[nums.length - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

标题：二分查找汇总
作者：Yi-Xing
地址：http://zyxwmj.top/articles/2021/02/15/1613399455333.html
博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！