基础二分查找总结

前言

由于我在学习二分查找的过程中处于会了忘,忘了复习的状态,因此总结一套适合自己记忆的模板。建议先看参考资料(^{[1,2,3]}),理解二分查找各种细节的由来。

  1. 二分查找又死循环了?【基础算法精讲 04】
  2. 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找
  3. 我写了首诗,让你闭着眼睛也能写对二分搜索

左闭右开的形式:循环条件一定是 while(left 。由于左闭,所以 left = mid + 1;。由于右开,所以 right = mid;。最后循环结束时,left == right

左闭右闭的形式:循环条件一定是 while(left 。由于左闭,所以 left = mid + 1;。由于右闭,所以 right = mid - 1;。最后循环结束时,left == right + 1

确保上面段话能理解,为了方便记忆,优先采用左闭右开的形式。因为循环结束时,left == right,我觉得简单一点。

基础的二分查找

力扣链接:704. 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

左闭右开代码实现

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;  // 定义target在左闭右开的区间里,即:[left, right)
        while(left  target){  
                right = mid;  // target 在左区间,在[left, mid)中
            }else{  // nums[mid] == target
                return mid;  // 数组中找到目标值,直接返回下标
            }
        }
        return -1;  // 未找到目标值
    }
}

左闭右闭代码实现

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;  // // 定义target在左闭右开的区间里,即:[left, right)
        while(left  target){
                right = mid - 1;   // target 在左区间,在[left, mid - 1]中
            }else{
                return mid;  // // 数组中找到目标值,直接返回下标
            }
        }

        return -1;  // 未找到目标值
    }
}

lower_bound 和 upper_bound

lower_bound

lower_bound 含义:

  • 返回第一个大于等于 target 的位置,如果所有元素都小于 target,则返回数组的长度。
  • 在不改变原有排序的前提下,找到第一个可以插入 target 的位置。

左闭右开代码实现

int lower_bound(int[] nums, int target){
    int left = 0, right = nums.length;
    while(left 

对于 nums[mid] == target 的情况:
此时找到一个目标值 target,然而左边可能还有 target。由于要找的是第一个大于等于 target 的位置,所以应该向左区间继续查找,因此与 else 分支合并。

左闭右闭代码实现

int lower_bound(int[] nums, int target){
    int left = 0, right = nums.length - 1;
    while(left 

这里和左闭右开形式不同,左闭右开 left == right,不用纠结。这里 left == right + 1,有时候搞不清楚是返回 leftright,还是 left - 1......

这里有个方便记忆的小技巧,假设 leftright 都指向 target,再看下一步的结果。

比如下面这个例子,target == 3lower_bound 要求的结果就是红色的3。


基础二分查找总结插图

此时 left == right,根据代码,应该执行 right = mid - 1; 这条语句,执行之后,如下图所示。

基础二分查找总结插图1

此时,left == right + 1,循环结束,结果应该为 left,所以 return left;

upper_bound

upper_bound 含义:

  • 返回第一个大于 target 的位置,如果所有元素都小于等于 target,则返回数组的长度。
  • 在不改变原有排序的前提下,找到最后一个可以插入 target 的位置。

左闭右开代码实现

int upper_bound(int[] nums, int target){
    int left = 0, right = nums.length;
    while(left 

对于 nums[mid] == target 的情况:
此时找到一个目标值 target。由于要找的是第一个大于 target 的位置,所以应该向右区间继续查找,所以与 if 分支合并。

左闭右闭代码实现

int upper_bound(int[] nums, int target){
    int left = 0, right = nums.length - 1;
    while(left 

lower_bound 类似,说一下记忆 return left; 的技巧。

假设 leftright 都指向 target,再看下一步的结果。

比如下面这个例子,target == 3upper_bound 要求的结果就是红色的4。


基础二分查找总结插图2

此时 left == right,根据代码,应该执行 left = mid + 1; 这条语句,执行之后,如下图所示。

基础二分查找总结插图3

此时,left == right + 1,循环结束,结果应该为 left,所以 return left;

可以看到,在左闭右闭的情况下,lower_boundupper_bound 都返回 left

lower_bound 和 upper_bound 的联系

可以发现,这两个函数只有 if 判断为相等的情况不同[6]。为方便记忆,在 if else 只有二分支的情况下,即把相等的情况归为 if 分支或 else 分支(不是 if ... else if ... else ... 三分支的情况)。

此时,lower_boundupper_bound 可以通过在 if 分支判断语句中增删 = 互相转化。

另外,upper_bound 可以直接复用 lower_bound
对于非递减整数数组,(>x) 等价于 (geq x+1)[1]upper_bound 求第一个大于 target 的位置,就等价于 lower_bound 求第一个大于等于 target + 1 的位置。

因此,upper_bound 的另一种写法

int upper_bound(int[] nums, int target){
    return lower_bound(nums, target + 1);
}

所以,只要记 lower_bound 的代码就好了。

力扣相关题目

35. 搜索插入位置

力扣链接:35. 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

解法一
直接应用 lower_bound

class Solution {
    public int searchInsert(int[] nums, int target) {
        return lower_bound(nums, target);
    }

    int lower_bound(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left 

解法二
通过 upper_bound 转化

class Solution {
    public int searchInsert(int[] nums, int target) {
        int pos = upper_bound(nums, target);
        if(pos == 0 || nums[pos - 1] != target) return pos;  // target 不存在
        return pos - 1;  // target 存在,前一个位置就是 target
    }

    int upper_bound(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left 

直接记解法一就行了,解法二只是证明 upper_bound 也可以做,因为 lower_boundupper_bound 本来就有转化关系。

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

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

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

思路
第一个位置:就是 lower_bound 函数的含义。
最后一个位置:如果 target 存在的话,第一个大于 target 的位置减一就是 target 的最后一个位置。

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lower_bound(nums, target);
        if(start == nums.length || nums[start] != target) return new int[]{-1, -1};  // target 不存在
        int end = upper_bound(nums, target) - 1;
        return new int[]{start, end};
    }

    int lower_bound(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left 

69. x 的平方根

力扣链接:69. x 的平方根

给你一个非负整数 x ,计算并返回 x 的 算术平方根

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去

注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

思路
这其实就是一个 upper_bound 问题,对于 x = 8,二分区间应该在 [0,8],我们要在这些数的平方中找到第一个大于8的数,它左边的那个数的平方根就是答案。如下图所示,找到9(是第一个大于8的数),左边4的平方根2就是答案。


基础二分查找总结插图4

代码
直接应用 upper_bound,下面的代码会超出内存限制,但是方便我们理解它和 upper_bound 的关系。

class Solution {
    public int mySqrt(int x) {
        int[] nums = new int[x + 1];
        for(int i = 0; i 

左闭右开代码
由于 x + 1 可能溢出,所以要用 long

class Solution {
    public int mySqrt(int x) {
        long left = 0, right = (long) x + 1;  //左闭右开,所以是[0,x+1)
        while(left 

左闭右闭代码

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;  //左闭右闭,所以是[0,x]
        while(left 

367. 有效的完全平方数

力扣链接:367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数,如  sqrt 。

示例 1:

输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2:

输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

左闭右开代码
由于 x + 1 可能溢出,所以要用 long

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num + 1;  //左闭右开,所以是[0,x+1)
        while(left  num){
                right = mid;
            }else{
                return true;
            }
        }

        return false;
    }
}

左闭右闭代码

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1, right = num;  //左闭右闭,所以是[0,x]
        while(left  num){
                right = mid - 1;
            }else{
                return true;
            }
        }

        return false;
    }
}

二分查找进阶

以上是基础的二分查找类型,对于进阶的题目,把问题转化成二分查找是一个难点。

参考资料

  1. 二分查找又死循环了?【基础算法精讲 04】
  2. 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找
  3. 我写了首诗,让你闭着眼睛也能写对二分搜索
  4. C++中的upper_bound和lower_bound区别
  5. 34. 在排序数组中查找元素的第一个和最后一个位置
  6. 用Java实现C++::std中的upper_bound和lower_bound

以上是我个人的学习心得,能力有限,如有错误和建议,恳请批评指正!

文章来源于互联网:基础二分查找总结

THE END
分享
二维码