二分搜索专题

本文最后更新于：2023年3月5日凌晨

什么事二分搜索？

这里有一道十分标准的例题：704
对于一个有序（升序）的整型数组，如果我们要从中找出目标值，最直接的方法是从头开始遍历，但效率肯定十分低下，而且没有好好利用到所给的条件（数组已排好序）。
这时候就可以用二分搜索来找到目标值，试想一下猜数游戏，只要我们每次都取一个中间值，是不是很快就能够定位目标值呢？

如：目标是78，我们先猜1，第二次猜100，第三次猜50，第四次猜75，以此类推
这就是二分搜索最基本的思想。
然后看到上面给出的例题，根据描述，可以很快写出下面的代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while right >= left:
            mid = (right + left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:  # nums[mid] > target
                right = mid - 1
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else  // nums[mid] < target
            {
                left = mid + 1;
            }
        }
        return -1;
    }
}

那么这代码之中其实也有要点，那就是mid = (right + left) / 2、while (left <= right)、left = mid + 1和right = mid - 1，之后在对比其他题目的时候会详细说明。

在做二分搜索的时候，如果弄不明白该怎么定位目标值的话，一定一定记得画图辅助，不要用脑子硬想，容易出错效率还不高。

其他的二分搜索题目

35. 搜索插入位置

题目链接：35
先放一个最初版本的代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1;
        mid = 0
        while right >= left:
            mid = (right + left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:  # nums[mid] > target
                right = mid - 1
        if right == -1:  # 特殊情况
            return 0
        return mid + 1 if nums[mid] < target else mid

这就很好的体现了画图的重要性。但凡画一下图都不会写出最后几句那么复杂的代码。
将最后三行代码删除，换成return left即可。这也说明了要多关注下left、right和mid三个变量，这样才利于我们找目标值。

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else  // nums[mid] > target
            {
                right = mid - 1;
            }
        }
        return left;
    }
}

278. 第一个错误的版本

题目链接：278
这题也是建立在二分搜索基础之上的，但是我们需要找到第一个错误的版本，可以这样理解：找到第一个跟在False后面的True。
首先介绍最简单的思想，对于每次的mid，我们可以判断此版本是False还是True，如果是False，就找它后面的一个版本并判断，如果是True，就找它前面的一个版本判断。

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        mid = 0
        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                if not isBadVersion(mid - 1):
                    return mid
                else:
                    right = mid - 1
            elif not isBadVersion(mid):
                if isBadVersion(mid + 1):
                    return mid + 1
                else:
                    left = mid + 1

不过很明显的是代码存在一定漏洞而且调用API的次数多了。比如示例2，如果只存在一个版本的话，那个版本就是错误的，那其实不能调用isBadVersion(mid - 1)，这应该是没有意义的，但是确实有漏洞让我过了（目移）。
那么如何优化呢？仔细想想，在判断完mid是True还是False以外，我们就能够知道：

如果mid == False，那么<= mid的版本都应该是False

如果mid == True，那么>= mid的版本都应该是True
所以，我们把循环条件改成：while left < right，缩小的区间改为left = mid + 1，right = mid，最后left == right的时候，就是我们要找的第一个错误的版本。
上面的改动保证right不会指到False的位置，且left能够指到True和False的位置，如果还是不是很清楚的话，可以画图辅助。

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        mid = 0
        while left < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

其实这代码其中还有一个问题，但是由于上面使用的是Python语言，某些特性导致代码能过。看到题目给的提示1 <= bad <= n <= 2^31 - 1，所以如果是需要对变量进行类型定义的语言就会出错，因为在这行代码mid = (left + right) // 2中存在大数导致的溢出。
改成这样就好了：mid = left + (left + right) \ 2。不知道怎么来的就画数轴（画图真的很重要好吗）。
下面是C#代码：

public class Solution : VersionControl {
    public int FirstBadVersion(int n)
    {
        int left = 1, right = n, mid = 0;
        while (left < right)
        {
            mid = left + (right - left) / 2;
            if (!IsBadVersion(mid))
            {
                left = mid + 1;
            }
            else // IsBadVersion(mid)
            {
                right = mid;
            }
        }
        return left;
    }
}

167. 两数之和 II - 输入有序数组

题目链接：167
这题能用双指针，也能用二分搜索写，由于本文章是二分搜索专题，所以这里只写二分搜索解法。
抓住题目所说该数组已按非递减顺序排列，那么很快可以想到二分搜索，然后看到我们需要找到两个数，这两个数之和等于target，且数组中一定存在解，那我们就能够在二分搜索循环里面写判断找出答案。
那么对于第一个数，我们可以先固定，也就是外层循环遍历数组的每一个数，在除去固定的第一个数后的在其后面的剩余数组使用二分搜索来找到第二个数，找到后返回即可。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            left = i + 1
            right = n - 1
            while left <= right:
                mid = (left + right) // 2
                if numbers[i] + numbers[mid] == target:
                    return [i + 1, mid + 1]
                elif numbers[i] + numbers[mid] < target:
                    left = mid + 1
                else:  # numbers[i] + numbers[mid] > target
                    right = mid - 1