关于算法:说实话我觉得二分查找很难

47次阅读

共计 5616 个字符，预计需要花费 15 分钟才能阅读完成。

导语：二分查找是对一个有序数组的搜索算法，因为每次都是折半搜寻，所以工夫复杂度未O(LogN)，然而在编写二分查找时外面蕴含了一些细节，上面将给大家讲述一下如何利用二分查找找到目标值、第一个比目标值大的值和最初一个比目标值小的值。

一、判断是否蕴含目标值（简略二分查找）

比方当初给你一个有序的数组nums，问你数组内是否蕴含目标值target，这个能够套用最根底的模板

public boolean binary_search(int[] arr) {
    int left = 0, right = arr.length - 1;   // 细节 1
    while (left <= right) {                    // 细节 2
        int mid = (right - left) >> 2 + left;
        if (arr[mid] == target) {return true} else if (arr[i] > target) {right = mid - 1;                // 细节 3} else if (arr[i] < target) {left = mid + 1;                    // 细节 3}
    }
    return false;                            // 细节 4
}

挡你刷的二分查找题目比拟多，看的题解比拟多的时候可能会有上面的疑难

  1. 到底是 right 的初始值是 arr.length 还是arr.length - 1？
  2. while的条件到底是 < 还是<=？
  3. right和 left 什么时候须要加 1 减 1？
  4. 如果要返回坐标，应该返回啥

前面两个问题其实是第一个问题引出的，咱们先解决第一个问题

  1. right是 arr.length - 1 还是 arr.length，下面的例子是arr.length - 1，取arr.length - 1 能够认为是在对区间 [left, right] 进行搜寻（两边闭合），如果让 right 等于 arr.length，那么right 曾经越界了，所以能够认为他是在对 [(left, right) 进行搜寻（左闭右开）

    留神 right 的取值会影响框架的其余地位

  2. while中 < 和<=次要体现在终止条件的不同，如果是 <，他的终止条件是left == right，如果是<=，则是left + 1 == right，不难发现< 不会解决 left == right 的状况，如果你应用了 <，须要多思考left==right 的状况

    如数组{1, 2, 3, 4, 5}, target = 5, 如果 while 修的是 <，返回的是 false

    如果硬是要用 <=，其实咱们曾经晓得他漏了判断left==right 的状况了，咱们只有在最初补上就行

    return arr[left] == target;

  3. 最初就是 left 和right加 1 减 1 的时了，需不需要加一减一取决于你的 right 是怎么定义的

    1. 如果是两边闭合的，当你检测完 mid 不是你想要的，下一步应该查看 [left, mid - 1] 和[mid + 1, righjt]呀，
    2. 如果是做闭右开，当你查看完 mid 不是你想要的值，下一步应该查看 [left, mid) 和[mid + 1, right)呀，所以 right 不必加 1

所以二分查找怎么写是由 right 的取值决定的

二、找到目标值坐标否则返回 -1

有了下面等到根底，咱们能够很快的写出代码

  • right = arr.length - 1

    代码如下：

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

  • right = nums.length

    代码如下

    public int binarySearch(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 {right = mid;}
    }
    return -1;
}

这里还是比拟容易了解的

三、找到第一次呈现指标元素的下标

例如给定一个数组 [11, 22, 33, 44, 44, 44, 55]，若target 等于 44，二分查找的后果应该为 3，这个时候咱们能够先用下面第二点的代码找到 44，而后往左边始终找，咱们也能够再二分查找模板上进行大量批改实现该性能

同样分成两种状况：

  • right = arr.length - 1

    这时是对两边闭合的区间进行搜寻，咱们只须要改一下原来的模板就行了

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

    为什么最初返回的是 left 呢，大家能够剖析一下：如果 target 存在于数组中，最初一次循环时 left 和right都指向 target，循环完结后right 通过 mid(left) - 1，所以left 才是目标值，如果目标值不在数组里，最初一次循环 left 和right都会指向第一个比目标值大的数，right被减去 1 后不再循环，最终返回的 left 能够了解为 数组中比目标值的数的个数，也能够认为是寻找大于等于目标值的数的索引，则个语义很重要

    如果题目要求找不到返回 -1，那么就须要加上一些判断。依据下面的剖析，left的取值范畴应该是 [0, len]，因而咱们须要判断left 等于 len（当target 大于这个数组所有的数，最初 left = mid + 1 所导致），或者 left = 0 然而 target != nums[0]（当target 小于所有数，最初 left = 0 所导致），又或者目标值在数组范畴里却不在数组中，那就是target != nums[left]，所以咱们徐娅加上两个非凡判断

    残缺代码如下：

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

  • right = arr.length

    如果对返回值没有作要求，代码如下：

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

    最初为什么返回 left 呢？如果目标值在数组中，最终 left = right 且会指向第一个 target，如果目标值不在数组中，最初一次循环时left 和right会指向第一个比目标值大的数，这其实和下面的状况雷同，最终返回的 left 能够了解为 数组中比目标值的数的个数

    如果要返回 - 1 呢？咱们也要思考 keft 的取值范畴，应该是[0, len]，所以当目标值比数组元素大时，left = right = len，当目标值比所有制小的时候left = right = 0，所以这次的判断和下面的一样

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

大家要思考当目标值比数组所有值都大的状况 left 和right指向哪里，最初应该是走 mid = left，走arr[mid] < target 的分支，letf = mid + 1，left等于 right 等于arr.length

四、找到最初一次呈现指标元素的下标

同样的，咱们来找一下最初一个指标元素

  • right = arr.length - 1

    代码如下

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

    大家剖析一下，最初咱们应该返回的是什么，应该是 left - 1，如果目标值在数组里，最初一次遍历left = right = 最初一个数字，而后left 被 +1，所以是 left - 1 or right。如果目标值不在这个数组中，最初一次迭代left = right= 第一个比目标值大的数的索引，最初饭返回的是left - 1，能够了解成 比目标值小的最初一个元素的索引

    如果要返回 – 1，咱们能够看看 right 的取值范畴应该是 [-1, len - 1]，如果目标值太小，right 应该是 -1，如果太大，right应该是len，所以残缺代码为

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

    // left = right + 1, right 指向的如果越界了
    if (right < 0 || arr[right] != target) {return -1;}
    return right;
}

  • right = arr.length

    如果是这种状况，代码应该是

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

    为什么是 left - 1 呢，设想一下当初 mid 指向目标值，当初 left = mid, right = mid + 1，mid 趋势是目标值，最初left = mid + 1，所以目标值在left - 1。如果目标值不在数组中，left = right = 第一个比目标值大的数，所以返回的是 最初一个比目标值小的数的索引

    如果你心愿返回 -1，left的取值范畴是[0, len]，如果目标值太大，这时候 left 应该是len·，如果太小，left = right = 0，综上，代码如下

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

    if (left == 0) {return  -1;}

    return arr[left - 1] == target ? left - 1 : - 1;
}

五、理论利用

形如：

for i in range(num1): 
    for j in range(num2)

这种工夫复杂度为 O (N2) 的找最目标值问题，都能够用二分查找解决，其中寻找左边界的二分查找用的最多，上面是 LeetCode 中常见的题目：

  • LeetCode 875 爱吃香蕉的 CoCo，
  • LeetCode 1011 在 D 天送达包裹的能力
  • LeetCode 410 宰割数组最大值

当然啦，二分查找能够和其余算法联合，例如高楼丢鸡蛋问题也是能够应用二分查找优化的，写完本文，我对本人的要求是把握剖析边界的办法以及学会寻找大于等于目标值的二分查找

参考

本文大量参考博主 labuladong 的文章，平时仓看他的文章，写得很好，大家有趣味能够去看看

  • 我作了首诗，保你闭着眼睛也能写对二分查找，labuladong https://mp.weixin.qq.com/s/M1…

正文完
算法
发表至： 算法
2021-04-08
 0
关于算法:MCD4710-Algorithms-讲解
关于算法:每日一题翻转子数组得到最大的数组值
关于算法:不知道蓄水池抽样算法那就进来看看吧
关于算法:LeetCodeGolang-647-回文子串