算法修炼之路(四) —— 二分搜索

      二分搜索，也叫折半查找，是一种采用分治思想的搜索算法。采用二分搜索的前提是所查找的线性表必须采用顺序存储结构，且表中元素按关键字有序排列。二分搜索充分利用了元素间的次序关系，每次搜索过程不断的对序列折半查找，根据中间位置的值缩小搜索的区域，把搜索过程的时间复杂度降低到O(logn)。二分搜索的实际运用千变万化，接下来让我们一起来探索这些经典的二分搜索算法。

1.用二分搜索法在排好序的无重复元素数组中查找某一元素的位置

      这道题应该算是运用二分搜索法最简单的题目了，我们只需要在折半查找过程中与所要查找的数进行大小比较，就能很快准确的找出该元素，我们可以直接用迭代来实现这个算法：

      

       当然，用递归的方式也同样可以实现这个算法：

 

2. 用二分搜索在有重复元素的数组中找出最先出现的某个数的位置

      这道题相比上一道题多了一步判断条件，即查找到的元素可能不是在数组中首次出现的，因此我们不能简单的把某次循环中符合条件的mid返回。拿数组[ 1，1，2，2，2，3，7，9，10 ] 举个例子，假设我们要在该数组中查找第一个出现的2的位置。在第一次搜索过程中，我们的mid会取到中间位置为5的2，此时我们能保证位置5的2肯定比右边的2先出现，但不能保证左边没有比它更早出现的2。

 

       因此我们得继续在左边部分查找，让right等于当前的mid，而让mid继续更新：

      此时我们发现下一个mid也符合条件，但还不能确定左边有没有比它更早出现的2，于是我们继续二分搜索：

      此刻的序列已经不能再细分了，我们发现此时mid比查找元素2小，说明在mid右边一位的right，就一定是2第一次出现的位置，我们返回right的位置。

      那如果数组不是[ 1，1，2，2，2，3，7，9，10 ] 而是 [ 1，2，2，2，2，3，7，9，10 ] 呢？数组到最后会是这种情况：

      因为mid大于等于2，这时我们还可以继续更新right，让它等于mid，然后left和right相邻结束循环：

      此刻和上一种情况一样，直接返回right也是正确的，但如果此刻的left也是2呢，最后的情况就会变成这样：

      显然，如果我们直接返回right，就会把真正第一次出现2的left给忽略了，这显然是错误的。因此，在返回right之前，我们要先判断左边的left是否符合条件，如果走到最后无法再二分时的left符合条件，就说明left一定才是第一次出现的。

      这道题的代码实现方式如下：

 

3. 求旋转数组的最小值：给定一个排好序的数组如 [ 1，2，3，4，5，6 ] ，在某个部位将数组分割然后交换位置如 [ 3，4，5，6，1，2 ]，用最快的算法找出交换位置后的旋转数组中最小的那个数。

    这道题的解法有很多，比如我们可以直接将数组进行排序然后返回第一个数。在上一篇文章中我已对排序算法做出总结，最快的外部排序时间复杂度为O(n+k)，最快的内部排序时间复杂度为O(nlogn)。而另一种更快的方式解决这道题就是直接迭代遍历每一个数找出最小的那个，这样的时间复杂度为O(n)。

      若还想再快一点，那只有用时间复杂度为O(logn)的二分搜索法了。对于一个前后交换元素位置数组，我们在用二分搜索先进行判断二分的部分是否是排好序的，即先判断最左边的数字是否小于最右边。对于数组[ 5，6，7，8，9，10，11，1，2，3，4 ]，在left >= right的情况下，说明数组不是排好序的。此时mid>=left，说明最小的数在mid和right之间。

      我们让left=mid，继续进行二分搜索。此时left依然大于right，数组还未排好序。但此时更新后的mid< left，说明最小的元素在left和mid之间。

      我们继续二分数组，让right=mid。此时left依然大于right，数组还未排好序。更新后的mid>=left，说明最小数字在mid和right之间。

      left继续更新为mid，此时left和right相邻，结束循环。

      跟上一道题不一样，这道题我们无需找到最小数出现的第一个位置，也不用担心最小数出现在第一位（因为是旋转数组，最小数不会出现在第一位），最后得到的right，就是我们想要的结果。所以我们不需要再进行left和right的比较，直接返回right对应的数，就是该数组的最小值。

      这道题的代码实现方式如下：

4. 在旋转数组中找出某个指定值的位置（可假设没有重复元素）。

      这道题其实是上一道题的扩展，只是我们多了一步查找目标target值的操作。用二分法在旋转数组中查找某个值，我们要先根据mid与left和right的比较来确定哪一部分是排好序的，进而根据target来调整left和right的值。

      对于数组 [ 4，5，6，7，8，9，1，2，3 ] ，假如我们要查找数字6的位置，我们首先对数组进行分割：

      首先arr[left]<arr[mid]，说明左半部分是排好序的。在排好序的这一部分，我们再根据数字6来确定left和right如何调整。因为此时满足arr[left] <= 6 <= arr[right]，就说明6是在left和mid之间，我们就让right=mid，继续进行二分搜索。

      此时arr[mid] 刚好等于6，是我们要找的值，我们直接返回mid就好了。

      再举个例子，假设我们要查找的数字是2，一开始还是对数组进行分割：

      首先确定哪一部分排好序，跟前面一样，还是左半部分，先在左半部分进行判断，我们根据数字2对left或right进行调整。因为2不满足arr[left] <= 2 <= arr[right] （即4<=2<=8的情况不成立），说明2不在这个排好序的左半序列中，我们让left=mid，在右半部分查找。

      调整完left的值后，我们再重复上述操作，先根据left和mid进行比较，来判断那一边是排好序的。arr[left] < arr[mid]，左半部分不是排好序的，我们就先在右半部分进行判断。此时arr[mid] <= 2 <= arr[right], 说明要查找的数字在右半部分，我们让left=mid继续进行二分搜索：

      此时arr[mid] 刚好等于2，我们直接返回mid的值。

      到达这一步时，假设我们要查找的值是3而不是2呢？ 3不满足arr[left] <= 3 <= arr[mid] ，我们还是让left = mid，此时left和right相邻，结束循环。

      循环结束时，我们发现right就是3的位置，直接返回right。

      那如果刚才我们要找的是数字4，搜索就会进行如下过程：

      最后left和right相邻结束循环时，我们发现此时left才是4所对应的位置。因此算法的最后，我们除了要对right进行判断，还要对left进行判断，才能输出正确的结果。

      这道题的代码实现方式如下：

5. 搜索插入位置：给定有序数组和一个目标值，如果在数组中找到此目标值则返回目标值的索引，如果没有找到，则返回目标值按顺序应该被插入的位置索引(假设数组中不存在重复数字)。

      对于数组 [ 1，7，8，12，13，15，20，30 ] 来说，假如我们的目标值是14，实际上我们返回的就是数字15的索引。搜索插入位置，实际上就是找出第一个大于等于目标值的数字的索引。如果没有，则说明该数比数组中所有数字都大，那就将它放在最后一位的下一位。这道题的代码实现方式如下：

6. 搜索数组中某个数字出现的区间：给定一个有重复元素的数组，找出某个重复元素出现的开始位置和结束位置。如果该数不存在，返回区间[-1,-1]。

      其实这道题也很简单，我们只需要运用两次二分搜索，对左右两边分别进行查找该数第一次出现的位置和最后一次出现的位置就可以了。两次的时间复杂度都为O(lgn)，所以总时间复杂度为O(lgn)+O(lgn) = O(lgn)。

      唯一需要注意的是对两次二分搜索的left和right调整，一个是往左搜索，一个是往右搜索，所以临界点的赋值要进行区分。

7. 给定一个排好序的无限序列，如 [ 1，1，2，2，2，3，3，4，4，4，5，5，6， …. ]，在该序列中找到某个数第一次出现的位置。

      首先题目告诉我们给定的是一个排好序的无限序列，说明我们不能直接用二分搜索进行查找，因为我们无法确定序列的长度，right一开始自然无法取值。这道题可以直接从开头一个一个数的遍历，这样做的时间复杂度为O(n)，那能不能像前面的题目一样也用二分搜索呢？

      答案是肯定的。但用二分搜索，我们首先需要确定一个固定的区间范围。对于范围的查找，我们可以使用倍增法，如图所示：

      假如我们要在无限序列 [ 1，1，2，2，2，3，3，4，4，4，5，5，6， …. ] 中查找数字5第一次出现的位置。一开始我们可以将left设为0，right设为1，然后比较right与5，如果right < 5 ，我们让left和right继续往后移动。right每一次我们都让它成倍的移动，同时left移动到right的位置：

      当right移动到不能再翻倍移动时，我们就让它定在序列的最后一位。

      此时我们发现arr[right] > 5，说明5就在区间[ left，right ] 所包含的元素里，我们将这部分区间的元素获取出来返回一个新数组，然后对这个新数组调用我们之前写好的第二道题写好的二分搜索算法，就可以直接找到5第一次出现的位置了。当然，返回的索引是新数组的5所对应的位置，我们还要将它和left相加，才是原数组中5第一次出现的位置。

    倍增法找区间的时间复杂度为O(lgn)，用二分搜索的时间复杂度也为O(lgn)，所以这道算法的总时间复杂度为O(lgn)。

8.找出供暖设备的最小供暖半径：给定两个数组，一个数组存放房屋的位置，另一个数组存放供暖设备的位置。假设每个供暖设备的供暖半径都一样，请求出供暖设备的最小供暖半径。

      我们假设给定房屋位置数组为 [ 0，2，3，6 ]，给定供暖设备位置数组为 [ 1，4 ]。求最小供暖半径，我们可以先求出每个房屋离它最近的供暖设备的距离。

      对于房屋0，离它最近的供暖设备是1号，它们之间的距离为1。对于房屋2，离它最近的也是1号，它们之间的距离也为1。对于房屋3，离它最近的供暖设备是4，它们之间的距离为1。对于房屋6，离它最近的供暖设备是4，它们的距离为2。

      我们分别求出了每个房屋离它最近的供暖设备，因为每个供暖设备的供暖半径是一样的，我们接下来就要在每个房屋离供暖设备的最近距离中，取出最大的那一个距离，也就是2。这个距离即是供暖设备的最小供暖半径。

    这道题的思路我们已经出来了：首先找出每个房屋离最近的供暖设备的距离，接着再在这些最近的距离中取出最大的那个数作为最小供暖半径。找出离每个房屋最近的供暖设备，我们很容易想到的就是直接遍历每个供暖设备与每个房屋的距离了：

      假设houses的数组长度为m，heaters的数组长度为n，这种解法的时间复杂度为O(m×n)。

      第二种解法，我们使用二分搜索来找出离房屋最近的供暖设备。找出离房屋最近的供暖设备，我们可以通过它们的位置索引来搜索。用二分法对供暖设备进行查找，找出第一个在索引值上比当前房屋大的空调，即第一个位于当前房屋右边的供暖设备。

      但是，找到的这个供暖设备，可能并不一定是离房屋最近的。因为我们找到的是房屋右边第一个供暖设备，但在房屋左边第一个供暖设备可能离房屋更近，我们假设供暖设备的排列位置如下：

      假如我们要找离房屋3最近的供暖设备，通过二分搜索找到右边第一个供暖设备时，我们找到了供暖设备5。但实际上，供暖设备2才是离房屋3最近的。因此，在用二分法找到房屋右边第一个供暖设备后，我们还要将这个供暖设备与前一个供暖设备进行比较分析，判断哪一个才是离房屋最近的。

      用二分法找右边第一个供暖设备，实际上就跟我们第五道题搜索插入位置的思路是一模一样的，我们只需要稍加改动，就可以取得供暖设备的索引值：

      这种解法的时间复杂度为O(m×lgn)。

9.求一个数的平方根。

      这道题非常简单，这里就不写分析过程了，直接贴代码，一目了然：

      但是，上面这种解法只能解决开整数平方根的数，如9，16，25。对于非整数，用上述这种方法会出现错误。这里有另一种更高级的解法——牛顿法，可以准确的处理任何正数的开平方根：

      不像第一种解法在从1开始递增进行尝试，牛顿法是从输入的数字本身进行缩减。这种解法的具体原理就暂时不做讨论，我们只需要记住有这样一种解法就可以了。

10. 矩阵搜索: 在一个N × M的矩阵里,每一行都是排好序的,每一列也是排好序的,请设计一个算法在矩阵中查找一个数。

      这道题最简单的方法依旧是暴力**遍历每个元素，这样做的时间复杂度为O(m×n)。

      如果高级一点的话我们可以对每一行用二分搜索，对于一个矩阵，比如

                 

      虽然我们知道每一行最后一个元素比第一个元素大，但不同行最后一个元素不一定小于下一行第一个元素。所以我们只能一行一行的使用二分搜索，这一行找不到就切换到下一行。或者反过来一列一列的进行二分搜索，这一列找不到就切换到下一列。这样的时间复杂度为O(m×lgn) 或O(n×lgm)。

      那有没有更高效一点的解法呢？其实对于这道题，我们可以不用二分搜索。我们任取一个数，在它左边和上边的数肯定比它大，在它右边和下边的数肯定比它小，我们可以以此为切入点找到下一个搜索的位置。

      但每次比当前数小的数都有两个选择（左边和上边），比当前数大的数都有两个选择（右边和下边），我们能不能继续缩小查找范围呢？答案是肯定的。对当前数在大小比较上各自只有一个选择的，就是对左下角的点和右上角的点。

      我们拿左下角的12举例子，假设我们要找到数是5，对于12来说，5比它小，而比它小的数只能在它上边，我们往上走一行到达11。对于11来说，5比它小，而比它小的数也只能在它上边，我们继续往上走一行到达2。对于2来说，5比它大，而比它大的数只能在右边（下边已经可以不用考虑了，因为刚刚从下边上来），我们往右走到3。接着3再往右走找到数字5。

                 

      在最差的情况下，比如从左下角开始找到数字4，我们得走满一行的长度加一列的长度，所以这种解法的时间复杂度为O(m+n)，显然比前面的方法好得多。它的具体实现方式如下：

11. 找出数组中的重复数字: 在一个长度为n+1的数组里，所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。假设数组只有一个重复数，请找出这个重复数字，但是不能修改输入的数组。例如，如果输入长度为8的数组{2,1,5,4,3,2,6,7}，那么对应的输出是重复的数字是2。

      因为数组未排序，又不能改动输入的数组，这道题首先想到的解法，就是计数排序的思路了。即新建一个长度同为 n+1的数组，并把每一位都设为0。然后遍历输入的数组，将每一位对应的数字在新数组对应的索引位置上累加，最后新数组上大于1的那一位所对应的索引值，就是我们要找的重复数字。

      这种解法的时间复杂度为O(n)，空间复杂度也为O(n)。

      那假如题目要求我们空间复杂度为O(1) 时，还可以怎么做呢？我们可以使用二分法。首先我们在区间 [ 1，n ] 中搜索（注意这个区间不需要我们额外开辟，我们只需要遍历这个区间的数字就可以了），首先求出中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数，如果个数小于等于mid，则说明重复值在[mid+1, n]之间，反之，重复值应在[1, mid-1]之间，然后依次类推，直到搜索完成，此时的right就是我们要求的重复值。

      因为每次二分搜索后都对整个数组遍历了一次，这种解法的时间复杂度为O(nlgn)。

12.合并区间：给定一个区间的集合，将所有存在交叉范围的区间进行合并。例如输入区间[ [1，3]，[2，6]，[8，10]，[15，18] ]，因为区间 [1，3] 和 [2，6] 存在交叉范围，所以将它们合并为 [1，6]，最后输出 [ [1，6]，[8，10]，[15，18] ] 。

      对于给定的区间，如果是没有排好序的情况，例如[ [5，10]，[2，6]， [1，3]，[15，18] ]，如果我们直接去合并，显然操作起来十分麻烦：

                 

      因此，我们首先对每个区间进行排序，让他们按区间先后顺序排好，以便进行下一步操作：

                      

      接着我们就要对相邻区间进行比较了，合并区间分三种情况，第一种情况：当下一个区间第一位<=上一个区间最后位<=下一个区间最后位，我们就可以将两个区间合并为 [ 上一个区间第一位，下一个区间最后位 ] 。例如，对区间 [ 1，3 ] 和 [ 2，6 ] 进行合并为 [ 1，6 ]。

      第二种情况，当下一个区间第一位<=下一个区间最后位<=上一个区间最后位，我们就可以将两个区间合并为 [ 上一个区间第一位，上一个区间最后位 ]。例如，对区间 [ 1，7 ] 和 [ 2，6 ] 进行合并为 [ 1，7 ]。

      第三种情况，即类似 [ 5，10 ] 跟 [ 15，18 ] 区间合并的情况，两个区间没有交集，所以不用进行合并处理，直接跳向下一步对 [ 15，18 ] 和它下一个区间的合并处理。

      我们可以开辟一个新的数组，用来存放最后的合并结果。首先将第一个区间放入新数组第一位，然后将其与原数组第二位开始进行比较：如果出现情况一，我们就将新数组第一位的最后位改为原数组下一位的最后位；如果出现情况二，我们就无需对新数组进行任何操作，直接将其与原数组下下位进行比较；如果出现情况三，我们就把原数组该区间添加到新数组中，然后不再对新数组刚才那个区间操作，转向对新添加进来的区间进行操作。

      这道题的代码实现方式如下：

      这道题似乎没有用到我们的二分搜索，但实际上这道题有一个扩展，就是在合并好的区间里插入一个新的区间再进行合并，插入区间就可以用到我们的二分搜索方法了，然后接下来还是根据这道题的思路进行合并。题目比较简单，这里就不再进行扩展了。

      除了前面讲到的题目，今天其实还有一些关于二分搜索的题目，如找到两个有序数组的中位数、在横竖排好序的矩阵中查找第k大的数、高楼扔鸡蛋测楼层等。因为时间有限，今天就暂时写到这里，这些题目留待以后有机会再做补充。下次算法专题将讲解分治法，欢迎继续关注。