【算法】二分查找模板

基本使用

下面是二分查找的最基本形式, 其原理是通过判断中间元素与目标值的大小来确定搜索方向的, 这种方法不需要后处理, 因为该方法在搜索目标元素的时候会不断向两侧偏移, 倘若找不到目标元素, 索引会偏移到数组末尾.

基本特征

• 初始条件：left = 0, right = length-1
• 终止：left > right
• 向左查找：right = mid-1
• 向右查找：left = mid+1

模板代码

def binarySearch(arr: List[int], target: int) -> int:
    lo,hi = 0,len(arr)-1
    while lo <= hi:
      mid = (lo + hi) // 2
      if arr[mid] > target:
        lo = mid + 1
      elif arr[mid] < target:
        hi = mid - 1
      else:
        return mid
    return -1 # 这种方法能够遍历所有元素, 当越界则说明找不到
1
2
3
4
5
6
7
8
9
10
11

查找左右边界

查找左右边界的模板适用于存在多个符合条件的数, 并要求找到索引最大/最小的情况. 对于出现重复的情况, 需要将边界值设置为中间值, 以不断逼近目标.

基本特征

注意, 在查找右边界过程中, 是通过mid不断向右偏移来查找右端点的, 因此需要取$mid=1+\lfloor \frac{left+right}{2}\rfloor$; 而在查找左端点的场景中, 是通过mid不断向左偏移来查找左端点的, 因此需要取$mid=\lfloor \frac{left+right}{2}\rfloor$

查找左边界

• 初始条件：left = 0, right = length-1
• 中间值: mid = (left + right) / 2
• 终止：left == right
• 向左查找：right = mid
• 向右查找：left = mid+1

查找右边界

• 初始条件：left = 0, right = length-1
• 中间值: mid = 1 + (left + right) / 2
• 终止：left == right
• 向左查找：right = mid - 1
• 向右查找：left = mid

模板代码

def leftBinarySearch(arr: List[int], target: int) -> int:
    if not arr:
        return -1
    lo, hi = 0, len(arr)-1
    while lo < hi:
        mid = (lo+hi)//2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return hi if arr[hi] == target else -1


def rightBinarySearch(arr: List[int], target: int) -> int:
    if not arr:
        return -1
    lo, hi = 0, len(arr)-1
    while lo < hi:
        mid = (lo + hi) // 2 + 1
        if arr[mid] > target:
            hi = mid - 1
        else:
            lo = mid
    return lo if arr[lo] == target else -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

查找最接近的值

在二分查找过程中, 可能有目标值不在数组中的情况发生, 在这个过程, 我们只需要找到一个值i满足
$$\begin{gathered} \text{寻找左边界: } \\ \exists is.t\forall x\in arr[i:]x\ge target \\ \wedge \forall x\in arr[:i],x<target \\ \text{寻找右边界: } \\ \exists is.t\forall x\in arr[:i]x\le target \\ \wedge \forall x\in arr[i:],x>target \end{gathered}$$

基本特征

找左侧最接近的值

• 初始条件：left = 0, right = length
• 终止：left == right
• 向左查找：right = mid - 1
• 向右查找：left = mid

找右侧最接近的值

• 初始条件：left = 0, right = length
• 终止：left == right
• 向左查找：right = mid
• 向右查找：left = mid+1

模板代码

def leftBisect(arr: List[int], target: int):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo+hi)//2
        if arr[mid] < target:
            lo = mid+1
        else:
            hi = mid
    return lo


def rightBisect(arr: List[int], target: int):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo+hi)//2
        if target < arr[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20