【算法题常见解题模式(套路)】Binary Search (二分查找，二分法)

相信许多正在为算法面试做着准备刷着题的程序员都会有类似的焦虑：我刷够题了吗？还要再来点吗？到底刷到什么程度才够呢？

刷题究竟应该怎么刷？

1. 刷题绝不是死记硬背。
2. LeetCode 上总共近 1700 道题，这看起来很恐怖，实际上很多问题本质上是很类似的，不过是做了一些小的变化。99%不敢说，至少90%的算法题，对应的解题模式不外乎那十多种常见的套路。
3. 我们应该通过若干道题来总结掌握一个通用的解题模式，然后举一反三，去解决一批问题。

这边对常见的解题模式(套路)，分析了 相关问题如何进行识别，给出了 具体的模板，同时每个模式都列出了 若干经典题和高频题，在实战中加深理解。

P.S. 本文为个人刷题心得总结，如有问题，欢迎交流探讨

---

Binary Search（二分查找，二分法）

问题特点

• 问题的输入为某种意义上有序的数组【比如排序数组，旋转排序数组，或者对于某个条件满足OOXX排列的数组等等】
• 要求寻找 满足某个条件的 特定位置 的项【比如最后一个小于 target 的数的位置，第一个大于等于 target 的数的位置】。

方法思路

二分法基本思路（基本原理）

二分法，也就是二分查找，用二分的方式去查找。

简单来讲，二分查找的 核心思路 就是 取中间项进行判断，利用列表的有序性在 O(1) 的时间内将问题的规模缩小至一半（砍掉一半的项）【从 n 到 n/2 再到 n/4……，最终到 1，即查找完毕】，具体步骤如下：

• 根据左右端点计算出中点。最简单的方式：mid = (start + end) / 2，但这种方式可能会出现 整数越界，因此一般使用这种写法：mid = start + (end — start) / 2【Python没有这种顾虑】
• 判断中间项nums[mid]是否满足特定条件，利用列表的有序性砍掉剩余项的一半

二分法细节

二分法思路虽然简单，但是细节很魔鬼，稍不注意就可能导致死循环。

① 指针如何变化（要不要，能不能把 mid 给剔除掉？有时可以有时不行，需要结合具体问题进行分析）

• start = mid ？
• start = mid +1 ？

② 循环结束条件（两指针相邻？重合？交叉？）

• while start <= end（两指针交叉）？
• while start < end（两指针重合）？
• while start + 1 < end（两指针相邻）？

这边给出一个二分法的通用模板。

所谓“通用”，就是指 在各种情形下都不会出问题（比如陷入死循环等），可以 放心大胆地，闭着眼睛去用，从而可以减少思考复杂度，让你可以把注意力集中在算法实现上。

通用代码模板

三点要素，

1. 指针变化方式：start = mid
2. 循环结束条件：while start + 1 < end（两指针相邻时退出循环）。
   分析：不相邻时，中间至少还隔着一个数，可以正常缩小问题规模，相邻时，就立刻退出循环，所以 mid 无论如何都不会取到 start 和 end 上。
3. 循环结束对应两种情况，一种是 start 和 end 相邻，另一种是 start 和 end 重合（对应输入只有一项，直接跳过循环的情况），两种情况我们都可以当做 start 和 end 相邻去处理，即对nums[start]和nums[end]分别进行判断（判断的先后顺序因问题而异）。

以在排序数组中寻找target为例

class Solution:
    def search(self, nums: List[int], target: int) -> int:
    	if nums == []:
    		return -1
    	
        start = 0
        end = len(nums) - 1
        
        while start + 1 < end:
            mid = start + end // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid
            else:  # target < nums[mid]
                end = mid
        
        if nums[start] == target:
        	return start
        elif nums[end] == target:
        	return end
        else:  # 目标不存在
        	return -1

这边简单列举了几种常见查找情况下，nums[mid] == target 时应该如何分析和处理

• 查找第一个等于的数：等于时，左半段可能还有等于它的项，所以 砍掉右半段
• 查找第一个大于的数：等于时，大于它的只可能在右半段，所以 砍掉左半段
• 查找第一个大于等于的数：等于时，左半段可能还有等于它的项，所以 砍掉右半段

可以看到，第一个等于和第一个大于等于的处理方式是相同的，和第一个大于是相反的。

典型问题

① 查找目标第一次出现的位置 - First Position of Target

class Solution:
    def search(self, nums: List[int], target: int) -> int:
    	if nums == []:
    		return -1
    	
        start = 0  # or left, right
        end = len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid
        
        # 因为是查找first position，所以先判断nums[start]
        if nums[start] == target:
        	return start
        elif nums[end] == target:
        	return end
        else:  # 目标不存在	
        	return -1

② 统计比给定整数小的数的个数 - Count of Smaller Number

可以转换成

• 查找最后一个小于 target 的数字的位置，+ 1 即为答案
• 反过来说，也可以查找第一个大于等于 target 的数字的位置。
• 两者其实等效的（就只是返回值需不需要 +1 的区别），个人感觉 “带等于” 的更好分析一些

class Solution:
    """
    @param A: A list of integer
    @return: The number of element in the array that 
             are smaller that the given integer
    """
    def countOfSmallerNumber(self, A, queries):
        A = sorted(A)
        
        res = []
        for query in queries:
            res.append(self.count_smaller(A, query))
        return res

    def count_smaller(self, A, query):            
        start = 0
        end = len(A) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if A[mid] < query:
                start = mid
            else:
                end = mid
        
        if query <= A[start]:
        	return start
        elif query <= A[end]:
        	return end
        else:
        	return end + 1

③ 搜索插入位置 - Search Insert Position（35.简单）

同样可以转换成：

• 查找第一个大于等于 target 的数的位置
• 反过来说，也可以查找最后一个小于 target 的数的位置，+ 1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if nums == []:  # 如果nums为空列表
            return
        
        start = 0
        end = len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
            	start = mid
            else:
                end = mid
        
        if target <= nums[start]:
            return start
        elif target <= nums[end]:
            return end
        else:
        	return end + 1

④ 在排序数组中查找元素的第一个和最后一个位置 - Find First and Last Position of Element in Sorted Array（34.中等）

用两次二分法，分别找到 first position 和 last position。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if nums == []:
            return [-1, -1]

        # 查找元素的第一个位置
        start ,end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid
        if nums[start] == target:
            left_bound = start
        elif nums[end] == target:
            left_bound = end
        else:
            return [-1, -1]  # 目标不存在，返回 False
        
        # 查找元素的最后一个位置
        start ,end = left_bound, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid
        if nums[end] == target:
            right_bound = end
        elif nums[start] == target:
            right_bound = start
        
        return [left_bound, right_bound]

⑤ 第一个错误的版本 - First Bad Version（278.简单）

简单来讲就是寻找第一个 isBadVersion 为 True 的版本。

典型的给定一个 XXOO 的序列，寻找第一个 O 的位置的问题。

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start = 1
        end = n

        while start + 1 < end:
            mid = start + (end - start) // 2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid
        
        if isBadVersion(start):
            return start
        elif isBadVersion(end):
            return end

⑥ 寻找峰值 - Find Peak Element（162.中等）

二分法的本质

如果我们想用二分法来解决一个问题，那么就需要 将问题转换成二分法的框架，也就是 找到一个判断条件

• 我们可以通过这个判断条件，来确定目标项是在左半段还是右半段

这道题需要一些 数学知识：如果一个连续函数是先升后降的，那么它在中间至少有一个峰。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0

        start = 0
        end = len(nums) - 1

        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < nums[mid - 1]:
                end = mid
            elif nums[mid] < nums[mid + 1]:
                start = mid
            else:
                return mid
        
        if nums[start] < nums[end]:
            return end
        elif nums[end] < nums[start]:
            return start

⑦ 寻找旋转排序数组中的最小值 - Find Minimum in Rotated Sorted Array（153.中等）

思路一、暴力法

遍历数组，寻找最小值

思路二、二分法

对于旋转数组的题，数组中不存在重复元素这一条件非常重要，否则无法砍掉一半项（举个极端点的例子，111011111）

解决这个问题，需要利用到 旋转数组 (Rotated Sorted Array) 的性质。

旋转数组大概是这样的形状

我们可以把最小点转换为 第一个小于等于 nums[-1] 的点

为什么是第一个小于等于 num[-1] 的点，能不能是第一个小于 nums[0] 的点？

列举一下所有的特殊情况 就可以总结出来。

• 没有循环左移的情况，此时最小点等于 nums[0]
• 循环左移了一个位置，此时最小点等于 nums[-1]
• 数组只有1个数的情况

这样一来其实就变成XXOO的形式了。

class Solution:
    # @param nums: a rotated sorted array
    # @return: the minimum number in the array
    def findMin(self, nums):
        if nums == []:
            return -1
            
        start = 0
        end = len(nums) - 1
        target = nums[-1]
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] <= target:
            	end = mid
            else:
                start = mid
        
        if nums[start] <= target:
            return nums[start]
        else:
        	return nums[end]

⑧ 旋转排序数组的搜索 - Search in Rotated Sorted Array（33.中等）

思路一、二分，先确定前半段还是后半段

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1

        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            # mid 落在前半段上
            if nums[start] < nums[mid]:
                if nums[start] <= target < nums[mid]:
                    end = mid
                else:
                    start = mid
            # mid 落在后半段上
            else:
                if nums[mid] < target <= nums[end]:
                    start = mid
                else:
                    end = mid
            
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        
        return -1

思路二、先找分割点（最小值点）再作二分

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1

        min_index = self.find_min_index(nums)
        if nums[-1] < target:
            return self.binary_search(nums, 0, min_index - 1, target)
        return self.binary_search(nums, min_index, len(nums) - 1, target)

    def find_min_index(self, nums):
        start = 0
        end = len(nums) - 1
        target = nums[-1]
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] <= target:
                end = mid
            else:
                start = mid
        if nums[start] <= target:
            return start
        return end

    def binary_search(self, nums, start, end, target):
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid
            else:
                end = mid
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1