二分查找

前言

说到二分查找很多人都是耳熟能详，这个算法基本是每个工科生（不仅仅是计算机相关专业）的必备知识点，在各种算法的题目中出现的频率也是极高的。然而很多考题并不会简简单单的去让你实现是个二分算法，而是通过各种变形来考验同学们对二分查找算法的理解程度，比如在在排序数组中查找元素的第一个和最后一个位置以及数组中的第K个最大元素这两道题里面就要用到二分搜索来寻找边界点和逼近最后的正确答案。我猜大多数人可能和我以前一样也是仅仅大概知道二分搜索这个东西并且能够简单实现，但是对于二分搜索的变形并不清楚。这篇文章将从最简单的二分查找开始讲起，然后用两个简单的二分搜索的变形的题目来加深对二分法的理解，希望能够让大家透彻的理解二分搜索这个重要的算法。

简介

在计算机科学中，二分搜索，也称为半间隔搜索、对数搜索或二分截断，是一种搜索算法，用于查找排序数组中目标值的位置。二分搜索将目标值与数组的中间元素进行比较。如果它们不相等，则消除目标不能位于其中的那一半，并在剩余的一半上继续搜索，再次将中间元素与目标值进行比较，并重复此过程直到找到目标值。如果搜索以其余一半为空结束，则目标不在数组中。

在最坏的情况下，二分搜索的时间复杂度为，其中为有序数组的长度。有专门为快速搜索而设计的专用数据结构，例如哈希表，可以比二分搜索更有效地进行搜索。但是，二分搜索可用于解决范围更广的问题，例如，在数组中查找相对于目标数字的下一个最小或下一个最大的元素。

基础——二分查找

与其空讲不如直接用一个题目来演示，这是LeetCode第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

这是最基本的二分搜索，看到这道题，几乎本能地写下了答案：

public int search(int[] nums, int target) {
    int left = 0 , right = nums.length-1, mid;
    while (left <= right) {           // 循环结束条件 ?
        mid = (left+right) / 2;
        if (target == nums[mid])      // 发现目标元素
            return mid;               // ?
        else if (target < nums[mid])  // 目标在左半区
            right = mid-1;            // ?
        else                          // 目标在右半区
            left = mid+1;             // ?
    }
    return -1;                        // 找不到目标
}

简单解释一下代码的逻辑：

while (left <= right)

循环结束的条件，当left==right的时候，说明范围已经缩减到了最后一个能够寻找的值，不管有没有找到，结束了这次循环之后，整个搜索都应该结束（left>right没有意义了）

mid = (left+right) / 2;

每次都取中间的一个元素，在这里左右相加可能出现溢出的情况，可以用mid = left+(right-left) / 2;来代替。注意这个地方可能出现left==mid的情况，在后面会提到。

if (target == nums[mid]) return mid;

当找到这个元素的时候就返回这个位置的索引。

else if (target < nums[mid]) right = mid-1;

目标元素比中间位置元素的位置还要小，那么就以mid-1作为右边界继续搜索。注意这里的mid是包含在原来的查找范围内的，所以需要排除mid继续搜索。

else left = mid+1;

目标元素比中间的大，把mid元素排除掉，再从mid右边一个元素mid+1开始寻找。

当循环终止的时候，如果找不到目标元素，一定是left>right，从逻辑内的计算可以发现一定是left==right+1。因为最后一个循环一定是left==right==mid，在经过下面的right=mid-1或者left=mid+1计算之后，得到left==right+1。

OK，现在我们花了大概30秒的时间把代码写了下来，然后测试通过————有没有感觉这是一段藏在我们工科生内心里面的代码，不用多想就能写出来！不过先别高兴，这里我就有点疑惑，如果数组中存在重复的目标元素，那么这段代码返回的索引是左边元素还是右边的还是中间的？！我们来试一下：

两个9：

输入：nums=[-1,0,3,5,9,9,12] target=9
输出：5

三个9：

输入：nums=[-1,0,3,5,9,9,9,12] target=9
输出：5

四个9：

输入：nums=[-1,0,3,5,9,9,9,9,12] target=9
输出：4

四个9（修改其他元素）：

输入：nums=[-1,9,9,9,9,10,11,12,13] target=9
输出：4

所以从上面的例子可以看出来，随着9的增加，最后返回的索引的位置可能是左边也可能是中间的也有可能是右边的，至于到底应该是哪个位置的取决于9的数量以及在数组中的位置，上面这段代码唯一能做的就是就到目标元素的其中一个索引（出现重复则不能确定索引位置相对于其他重复元素的位置），如果找不到就返回-1。

那么现在新的挑战过来了，如何找到元素在排序数组中第一个位置和最后一个呢？

进阶——在排序数组中查找元素的第一个和最后一个位置

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

给定一个按照升序排列的整数数组nums，和一个目标值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]

一看这个题目就是二分法来做，最简单直接的方法就是用上面一个案例的二分法找到这个元素，然后从这个元素位置同时向左向右开始遍历，直到直到第一个不是这个目标值的元素，就是边界了。虽说这个方法用了二分法并且在寻找元素的时候时间复杂度做到了，但是如果这个数组里面所有元素都是目标元素，比如把第一个示例改成[8,8,8,8,8,8]，那么在找到这个元素之后，还是要遍历整个数组，时间复杂度就降低到了了，那么要如何只用两次二分搜索就找到上下边界呢？

二分搜索是有一套自己的模板，前一个案例用到的是基本的套用，在上一题的代码里面有四个?，而这个四个就是整个二分搜索的关键点，修改了这几个值就是修改了逻辑。

那么我们在逻辑上再重新梳理一下这个情况下二分搜索逻辑，现在我们要寻找左边界：

1. 如果target==nums[mid]，那么左边界可能就是mid，也有可能在mid的左边
2. 如果target<nums[mid]，那么左边界一定在mid左边
3. 如果target>nums[mid]，那么左边界一定在mid右边

看上面的第一个和第二个条件，归纳一下可以得出：如果target<=nums[mid]的时候，target可能在mid这个位置，也可能在mid的左边，下一步的right直接用mid就行了，不用减一。所以我们可以把while循环内部的逻辑缩减成下面这个样子：

mid = (left+right) / 2;
if (target <= nums[mid])
    right = mid;            // 两个条件合二为一
else
    left = mid+1;        // 保持不变

每次循环都能够缩小范围并且始终把左边界的位置控制在left和right中间，直到循环结束。

似乎找到了一丝曙光，有点头绪了，不过我们好像刚才把return语句给删掉了，返回的值到底在哪？回答是返回值在循环结束之后处理，根据边界赋值的条件，我们在循环里面没有办法判断是否已经找到了这个元素，能使用的只是循环结束之后的left和right两个值（其实只有一个，因为循环结束之后left==right）。

可是这个循环真的能够结束吗？我们有循环结束的条件left<=right，如果left==right==mid并且target==nums[mid]，这个循环不就死循环了？所以这里为了不让循环死在这个地方，修改一下条件为left<right，分析一下这个循环：如果left+1==right，那么mid=(left+right)/2=left，则有：

• 如果target<=nums[mid]，right=mid=left，循环结束
• 如果target>nums[mid]，left=mid+1=left+1=right，循环也结束

所以如果把循环结束的条件变成left<right，无论如何循环都会结束。那么现在要根据循环结束之后的left和right这个两个值，找到边界值。根据前面的筛选条件，我们到了最后一层的循环，left+1=right，范围缩小到了最后两个元素，只有几种结果，我们定义num1<target<num2，num1和num2都是数组里面的元素：

1. [num1, target] 此时nums[mid]=nums[left]=num1，判断条件target>nums[mid]成立，left=mid+1，得到最后的循环结束的left的位置的值就是target
2. [target, num2] 此时同样nums[mid]=nums[left]=target，判断条件target<=nums[mid]成立，right=mid，最后得到nums[left]=nums[right]=target
3. [target, target] 这个情况和第二种情况一样，判断条件target<=nums[mid]成立，得到nums[left]=nums[right]=target

所以从上面的讨论可以看出，当数组中存在一个或者多个target元素的时候，一定能够通过这个方法找到target的左边界为left；如果不存在的时候，循环终止，这个left位置的值肯定不是target。

所以最后寻找左边界的代码如下：

public int searchRangeLeft(int[] nums, int target) {
    int left = 0 , right = nums.length-1, mid;
    while (left < right) {         // 注意
        mid = (left+right) / 2;
        if (target <= nums[mid])  // 在左侧
            right = mid;
        else                      // 在右侧
            left = mid+1;
    }

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

这个时候从上面这个代码一定能够找到元素的左边界，同样的我们根据上面的分析过程，完成右边界的代码：

// 错误代码
public int searchRangeRight(int[] nums, int target) {
    int left = 0 , right = nums.length-1, mid;
    while (left < right) {
        mid = (left+right) / 2 + 1 ;
        if (target >= nums[mid])  // 右边界在右侧 和上面代码不同的地方
            left = mid;           // 这里变成了left
        else                      // 右边界在左侧
            right = mid-1;        // 这里变成了right
    }

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

然后把运行一下nums = [5,7,7,8,8,10], target = 8这个测试用例发现出现了死循环！WTF！发生了什么！明明和寻找左边界的代码一样啊！问题就出在mid = (left+right) / 2 ;这行代码里面。我们回头看一下循环的终止条件的分析：

• 如果target<=nums[mid]（改成了target<nums[mid]），right=mid=left（根据mid=(left+right)/2来的，所以此时right=mid-1=left-1），循环结束
• 如果target>nums[mid]（改成了target>=nums[mid]），left=mid+1=left+1=right(变成了left=mid=right-1，此时left<right仍然成立，所以循环会一直进行下去)，循环也结束

在寻找左边界的时候如果left=right-1，计算出来的mid值一直是left，这样能够让mid的位置始终靠左；但是在计算右边界的时候，需要让mid的位置向右靠，终止循环，所以此时mid的计算公式要改成mid = (left+right) / 2 + 1，最后让mid=right才能最后让left==right。修改之后代码如下：

// 正确代码
public int searchRangeRight(int[] nums, int target) {
    int left = 0 , right = nums.length-1, mid;
    while (left < right) {
        mid = (left+right) / 2 + 1 ;   // 注意
        if (target >= nums[mid])
            left = mid;
        else
            right = mid-1;
    }

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

组合上面两个方法就可以得到我们最后的结果了。上面讲的两个方法，也可以用来代替案例一中的二分搜索，毕竟在案例一只要找到了这个元素就可以了，不在乎是左边界还是有边界。

好了，感觉我们已经彻底学习完了二分搜索并且完全理解了，可以关上电脑好好休息了。但是——不！Hold On！我还有一个问题：如果在有序数组里面不存在这个target，我们想把它插入到这个数组里面应该怎么做？上面的代码应该怎么修改。

进阶——搜索插入位置

这是leetcdoe第35题搜索插入位置

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

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

示例1：

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

示例2：

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

看到这道题，感觉和案例二特别类似，我们找到元素的左边界不就可以了，但是我们不知道当元素不存在的时候，返回的位置是不是正确的位置，所以我们修改一下上面的searchRangeLeft方法如下：

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

    return left;    // 这里修改返回的结果
}

然后运行一下代码测试一下示例1和示例2，发现返回的结果果然是正确的，分别是2和1，接下来不管我们怎么修改target的值只要是target<=6都能够得到正确的结果，当target==8的时候，返回了3，是错误的结果。所以直接照搬代码肯定不行，那我们要怎么修改代码呢？记住我们现在要寻找的坐标是第一个大于等于target的元素的坐标

还记得案例二里面的分析方法吗，我们再分三种条件来分析一下：

1. 如果target==nums[mid]，找到了等于target的元素，保留下来mid位置，设置right=mid
2. 如果target<nums[mid]，通过以下两个结论可以得到right=mid
   • 如果target存在，一定在mid左边
   • 如果target不存在，第一个大于等于target的元素可以能是nums[mid]，也有可能在mid的左边
3. 如果target>nums[mid]，通过以下两个结论可以设置left=mid+1
   • 如果target存在，一定在mid右边
   • 如果target不存在，第一个大于等于target的元素也一定在mid的右边

这里发现逻辑和原来的寻找左边界的时候情况一模一样，但是对于返回的结果是否正确还不确定，还要继续讨论一下。

对于target的值我们分三种情况讨论：

1 当target<nums[0]也就是当target比数组里面的最小值还要小的时候，可知在循环中每次都进入第二个判断条件，最后得到的left为0，符合预期。

2 当target>nums[nums.length-1]的时候，在循环中每次都进入最后一个判断主体，最后得到left=num.length-1，也就是right的初始值，这样得到的答案是明显不对的。所以在进入这个循环之前，我们可以直接判断一下target的值是否大于数组最右侧的值，如果是的就直接返回nums.length；如果不是才进入下面的循环。

3 如果target处于元素中间的位置，就进入接下来的分析。

这里我们仔细看这个循环

while (left < right) {
    mid = (left+right) / 2;
    if (target <= nums[mid])
        right = mid;
    else
        left = mid+1;
}

在进行最后一轮循环的时候，left==right-1，我们定义两个元素num1=nums[left]和num2=nums[right]，并且一定满足num1<=num2，在这个讨论中我们可以忽视target存在于数组中的情况（我们在上面已经讨论过了这个计算结果的正确性），target和这两个值之间只有可能有下面三种情况：

1. target<num1<=num2 可得target<nums[mid]=nums[start]=num1，所以进入第一个判断条件，最后得到nums[left]=nums[right]=num1，也就是第一个大于target的元素
2. num1<target<num2 可得target>nums[mid]=nums[start]=num1，所以进入第二个判断条件，最后得到nums[left]=nums[mid+1]=nums[right]=num2，这也是第一个大于target的元素
3. num1<=num2<target 这种情况不可能出现在这个循环里面，因为根据循环的条件决定了不可能出现right所在元素的值小于target

所以从上面就可以判断出最后得到的left的值就是第一个大于等于target的元素的位置的索引。

归纳一下上面的代码可以得到：

public int searchInsert(int[] nums, int target) {
    int left = 0 , right = nums.length-1, mid;
    if (target > nums[nums.length-1])   // 循环前置条件
        return nums.length;

    while (left < right) {
        mid = (left+right) / 2;
        if (target <= nums[mid])
            right = mid;
        else
            left = mid+1;
    }

    return left;
}

其实这道题还有一个小小的技巧，我们可以抛弃这个前置条件target<=nums[nums.lenght-1]，然后初始化right的时候设置成nums.length，这里其实我们是自己偷偷的把数组的最后面增加了一个值为无穷大的元素，target一定小于无穷大，最远也只能插入到这个位置，不会越界。而且也不用担心指针会溢出，因为mid值在计算的过程中永远不可能等于nums.length。

总结

二分搜索的核心就是循环结束条件和左右边界迭代规则，明白了如何确定这两点，二分搜索就能轻松为你所用。

二分搜索本身并不是特别难的一个知识点，但是是非常重要的一个概念，如果题目提到了或者暗示要用（或者更普遍的说类似甚至）的时间复杂度，首先应该想到二分，如果不能二分搜索，二分搜索的相关思想分治法也应该从脑袋里面出现。

这篇文章是二分搜索基础知识以及应用，在LeetCode上面还有其他的二分搜索精彩应用的题目，希望大家能够学习完这篇文章之后能够熟练使用二分搜索解决下面的问题

• 33.搜索旋转排序数组
• 74.搜索二维矩阵
• 153.寻找旋转排序数组中的最小值
• 378.有序矩阵中第K小的元素
• 483. 最小好进制
• 887.鸡蛋掉落
• 1103. 分糖果 II

更多内容请看我的个人博客

参考

二分查找算法细节详解
Binary search algorithm
Fractional cascading
Clean iterative solution with two binary searches (with explanation)