算法锦囊3：一文搞定二分查找-一一网

这是我参与更文挑战的第9天，活动详情查看：更文挑战

最近想把自己刷算法题的经验心得整理一下，一方面为了复习巩固，另一方面也希望我的分享能够帮助到更多在学习算法的朋友。

专栏名称叫《算法锦囊》，在讲解算法时会注重整体性，但不会面面俱到，适合有一定算法经验的人阅读。

这一次我们重点来看二分查找，这一部分的所有题目和源码都上传到了github的该目录下，题解主要用Python语言实现。

经典二分

先看一道最经典的二分法题目，来自leetcode的704. 二分查找。

算法如下：

初始化指针 left = 0, right = n - 1。
当 left <= right：
- 比较中间元素 nums[mid] 和目标值 target 。
- 如果 target = nums[mid]，返回 pivot。
- 如果 target < nums[mid]，则在左侧继续搜索 right = mid - 1。
- 如果 target > nums[mid]，则在右侧继续搜索 left = mid + 1。

直接上Python的代码

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

这里提一点，有很多leetcode的python题解，会在mid那里写成 mid = left + (right - left) // 2，说是防止大数溢出。

比如在Java语言里，int型的范围是 -2^32~2^31 ，即-2147483648 ~ 2147483647，下面的代码演示下溢出。

public class Test {
    public static void main(String[] args) {
        int end = Integer.MAX_VALUE;
        System.out.println(end+1); // 输出-2147483648
    }
}
复制代码

Java和C++需要这样考虑，但是Python不用。Python的整数没有大小限制，可以处理任意大小的整数，当然包括负整数。

举个代码例子，求2^1000，可以发现答案被正确计算出来了。

Python具体是如何实现存储长整数的，可看我参考资料的文章，这里不多做赘述。

x的平方根

接下来，来看一道二分法题目的变体，来自leetcode的69. x 的平方根。

题目很简单，实现 int sqrt(int x) 函数。如果有小数，则小数部分舍去，比如输入8，输出2。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            if mid * mid == x:
                return mid
            if mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1
        if left * left > x:
            return left -1
        else:
            return left
复制代码

我整体还是使用了二分查找的代码模板，在最后返回结果的时候，额外去确定了left和left-1该返回哪一个。

另一种解法是这样，由于我们最终答案是去尾，因此在得到最终的答案 ans后，也就不需要再去尝试ans+1 了。

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
复制代码

这道题虽然看上去简单，但其实很容易出错，尤其是对一些边界的处理，必要时多跑一些测试用例。

搜索旋转排序数组

接下来继续来看这道升级版的二分查找，33. 搜索旋转排序数组

虽然数组产生了旋转，但整体还可以用二分查找的思路来解决。

我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums)-1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1
复制代码