导语：二分查找是对一个有序数组的搜索算法，因为每次都是折半搜寻，所以工夫复杂度未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...