二分查找解题模式

作者:Windson Yang
更新时间:July 4, 2019
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明 www.enginego.org。

概述

二分查找是 Leetcode 常见的题型,难点有二,第一是编写正确的二分查找程序,第二是想到用二分查找来解这道题,后者明显更难。

辨别问题

先分析二分查找算法的使用场景:

从一个有限的递增区间中,找到符合要求的极值。

我们需要从题目中找到有限递增区间以及目标,先从最基础的二分查找程序开始,

Leetcode 704. Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

给定一个递增数组以及一个目标值,如果目标值在数组内,则返回其索引值,否则返回 -1。

Input: 
nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

有限递增区间是 [-1, 0, 3, 5, 9, 12],目标是找到值等于 9 的元素。

如果你不太熟悉二分查找,可以从这张 Gif 中观察查找的过程: binary_search

(引用自 https://brilliant.org/wiki/binary-search/)

这题的有限递增区间与目标值都非常明显,其中递增数组,返回目标值的索引,这两个词暗示着使用二分查找解答。不过一些题往往不会直接给出这些关键信息,所以也不容易想到可以使用二分查找解答。这里有几个例子,你可以试试在其中找出有限递增区间以及目标

  • 69. Sqrt(x)

    Implement int sqrt(int x).

    Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

    Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

    找到目标值的平方根,然后转成整数

    Input: 4
    Output: 2
    

    有限递增区间是 [0, 1, 2, 3, 4](0 到 目标值的值),目标是找到最大的数组中平方小于等于 4 的值。例子中,我们会先计算递增区间里 2 的平方与 4 的大小关系,然后更新搜索区间。

  • 1044. Longest Duplicate Substring

    Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)

    Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is “”.)

    给定一个字符串,返回最长的连续重复出现的字符串。

    Input: "banana"
    Output: "ana"
    

    有限递增区间是 [0, 1, 2, 3, 4, 5](零到字符串的长度减一),目标是找到最长的有重复出现的字符串。例子中我们先计算字符串长度为 2 的所有字符串是否有重复出现的字符串,如果有的话,我们尝试找更长的长度为 3 的字符串,更新搜索区间,直到循环结束。

  • 778. Swim in Rising Water

    On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

    Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

    You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

    Input: [[0,2],[1,3]]
    Output: 3
    
    Explanation:
    At time 0, you are in grid location (0, 0).
    You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
    You cannot reach point (1, 1) until time 3.
    When the depth of water is 3, we can swim anywhere inside the grid.
    

    有限递增区间是 [0, 1, 2, 3](矩阵的节点总数),目标是找到数组中最小的且能够到达右下角的合法值。例子中先计算 time 为 1 的时候能否到达右下角,可以的话,就更新区间,找更短的时间。

像我一开始说的,二分查找的程序本身并不难,但是想到这题可以用二分查找来解答并不容易,另外常见的几个使用二分查找的提示语分别是:

  1. 时间复杂度与 O(log(n)) 有关
  2. 所求答案有明确的上下界限范围。
  3. 题目描述中涉及到数据结构的和(如一个全部为正整数的数组,此时可以先计算累积和(保证是递增数组),然后使用二分查找)。

解题模式

如果我们足够幸运找到了递增区间与目标,那么就可以开始编写二分查找的程序了,解题模式比较直观,先从递增区间的中间开始,验证 mid 是否符合条件,然后根据返回值更新查找范围,每次缩小一半范围直到跳出循环,以下是伪代码:

function binary_search(array, target):
    left = 0
    right = length of array
    while left smaller than right
        mid = (left + right) / 2
        # 判断 mid 是否符合题目条件
        if is_valid(mid) is True
            return mid
        else if other condition
            left = mid + 1
        else:
            right = mid 


function is_valid(mid):
    # 返回 mid 是否符合条件的布尔值

以上是最基础的二分查找程序,只需要找到符合条件的值即退出循环,不过在上面的 Leetcode 例子中,大多需要找到极大值或者极小值,所以需要变形为:

function binary_search(array, target):
    left = 0
    right = length of array
    while left smaller than right
        mid = (left + right) / 2
        # 使用 left 保存上次符合条件的值
        if is_valid(mid) is True
            left = mid + 1
        else:
            right = mid 
    # 返回最后的合法值
    return left


function is_valid(mid):
    # 返回 mid 是否符合条件的布尔值

以上的程序实现起来并不难,不过初学者容易混淆一些边界条件导致死循环,我们这里通过分析两种正确的二分查找程序来说明如何编写正确的程序,给定数组:

[1, 2, 3, 4, 5]

两种实现方式区别在于右边界的初始值:第一种实现方式定义右边界为递增区间长度,第二种实现方式定义右边界为递增区间长度减一:

[1, 2, 3, 4, 5]
 |              |               
 left = 0          right = 5(递增区间长度,不可能是目标答案,不可达)

[1, 2, 3, 4, 5]
 |           |               
 left = 0       right = 4(递增区间长度减一,可能是目标答案,可达)

我们从右边界的可达性,可以推理出二分查找函数中的其他要点:

  1. 跳出循环条件:当左边界等于右边界时,因为右边界不可达,所以此时的左边界也不可达,所以查找结束,跳出循环。
  2. 右边界更新值:右边界不可达是在整个函数都不变的,所以在更新右边界的时候,应该更新为验证过的 mid,而不是 mid - 1。(因为 mid - 1 是可达的)

以下是两种形式的伪代码:

function binary_search(array, target):
    '''
    形式一:右边界不可达
    '''
    left = 0
    # 右边界等于区间长度
    right = length ofarray
    # 当左边界小于右边界时跳出循环
    while left < right:
        mid = (left+right) / 2
        if array->mid equal to target:
            return mid
        else if array->mid < target:
            left = mid + 1
        else:
            # 右边界更新为 mid
            right = mid

function binary_search_two(array, target):
    '''
    形式二:右边界可达
    '''
    left = 0
    # 右边界等于区间长度减 1
    right = length of array - 1
    # 当左边界小于等于右边界时跳出循环
    while left <= right:
        mid = (left+right) / 2
        if array->mid equal to target:
            return mid
        else if array->mid < target:
            left = mid + 1
        else:
            # 右边界更新为 mid - 1
            right = mid - 1
实现方式 右边界初始值 右边界是否可达 跳出循环条件 更新右边界
递增区间长度 不能 while left < right 等于 mid
递增区间长度减一 可以 while left <= right 等于 mid - 1

你可以试试解决 Binary Search 来验证自己是否正确理解,其中两种实现方式也有共同需要注意的地方,在代码段:

mid = (left + right) / 2
  1. 根据题目要求,可能需要改为 left += (right-left) / 2 的方式防止正整数溢出。
  2. 需要根据我们找的目标值是整数还是浮点数来决定是否使用整除,若目标值是浮点数,left 与 right 应该更新边界为 mid。(如果像之前一样更新为 mid - 1 或 mid + 1 的话,会错过 mid 到 mid - 1 / mid + 1 之间的可能答案)

原题分析

1044. Longest Duplicate Substring

如果我们知道这题是使用二分查找解答的话,那么只需要遵照上面的解题模式,找到递增区间,目标值以及 is_valid 函数即可。这道题的所求答案在 0 和 字符串长度减一之间,在例子 “banana” 中,答案一定是 0 到 5 之间,所以我们可以先猜测长度为 3 的所有字符串是否有符合条件的值,如果有的话,我们先保存下来,然后向右边找更长的字符串 4,在 “banana” 中,初始递增区间为 [0, 1, 2, 3, 4, 5] 我们先找出所有长度为 3 的字符串:

  • ban
  • ana
  • nan
  • ana

这里 “ana” 重复出现了,所以答案至少为 3。 我们减少搜索区间为 [4, 5],然后再继续找是否有字符串重复出现

如何查找重复字符串

最简单的方法是使用 hash table 或者字典来保存出现过的字符串,然后比对是否重复出现,例如:

hashmap = {}

ban -> not in the hashmap -> hashmap = {ban}
ana -> not in the hashmap -> hashmap = {ban, ana}
nan -> not in the hashmap -> hashmap = {ban, ana, nan}
ana -> in the hashmap -> return 'ana'

在 Leetcode 中,某些 testcase 会导致 Memory Limit Exceeded,所以需要我们自己实现简单的 hash table。不过本文主要说明二分查找,所以我直接使用 hash table。以下是 Python 代码:

class Solution:
    '''
    此答案会导致 Memory Limit Exceeded
    '''
    def longestDupSubstring(self, S):
        self.ans = ''
        res, lo, hi = 0, 0, len(S)
        while lo < hi:
            mi = (lo + hi + 1) // 2
            # 不同于简单的二分查找,我们要找的是符合条件的
            # 最大值或者最小值,所以当 is_valid 返回 True 的时候
            # 并不直接返回,得到答案,而是先保存当前符合条件的答案,然后持续更新
            pos = self.is_valid(mi, S)
            if pos:
                lo = mi
            else:
                hi = mi - 1
        return self.ans

    def is_valid(self, L, S):
        dic = {}
        for i in range(len(S)-L+1):
            if S[i:i+L] in dic:
                # 持续更新符合条件的答案
                self.ans = S[i:i+L]
                return True
            else:
                dic[S[i:i+L]] = True
        return False

总结

观察题目能否用二分查找是解题的第一步,需要观察题目,找到有限递增区间以及目标,第二部则是正确实现二分查找算法(注意右边界的可达性)。