二分查找

发表于 更新于 分类于 ，

1. 基础知识

算法简介

二分查找是在有序数组中寻找某一元素的查找算法，它的主要思想就是将搜索空间缩小为原来的一半。尽管二分查找的思想非常简单，但是很多人也容易出错，主要问题出现在代码对边界值的处理、比较符号带不带等号这些细节上。

算法流程

  • 设数组 arr = [0, 1, …, N]，初始化左边界 left=0，右边界 right=len(arr)-1，mid 为左右指针的中点；
  • 取出 mid 指向的元素，如果此元素为查找的元素，结束查找过程，并返回结果；
  • 如果 mid 指向的元素大于查找目标，因为数组有序，因此接下来查找 arr[left, mid-1]；如果此元素小于查找目标，那么接下来查找 arr[mid+1, right]；
  • 更新 left、right 和 mid，不断重复此过程，如果搜索空间为空，说明数组 arr 中不存在所要寻找的值。

复杂度分析

  • 平均时间复杂度 $O(\log N)$
  • 最坏时间复杂度 $O(\log N)$
  • 空间复杂度
    • 迭代实现： $O(1)$
    • 递归实现： $O(\log N)$

2. 基本的二分查找

一开始 7 小于 11，下一步需要缩小搜索空间为右半部分

14 大于 11，在上一步的基础上，缩小搜索空间为左半部分

找到 11 所在的索引，返回索引值 3

如上图所示，给定数组 arr=[2,4,7,11,14,27] 和 target=11 的查找流程，可用文字描述为：

  • 首先对 left 和 right 进行初始化 ，其中 left=0 ，right=len(arr)-1；

  • 进入二分查找的循环体中，结束循环的条件为 left<=right；

    • 计算 mid，mid=left+(right-left)//2，可以看做向下取整，这里没使用 (left+right)//2 ，因为 left 和 right 直接相加时可能会出现溢出的情况；
    • 判断 arr[mid] 和目标值的大小关系，如果相等，则结束查找流程，返回 target 的索引，即 mid；
    • 如果 arr[mid] 大于目标值，可以缩小搜索空间为 [left, mid-1] ，即令 right=mid-1；
    • 如果 arr[mid] 小于目标值，可以缩小搜索空间为 [mid+1, right]，即令 left=mid+1；
    • 如果满足循环的条件，则不断重复此过程。
  • 结束循环，如果没有找到目标值，返回 -1。

结束循环的条件是 left<=right，即我们的搜索空间为 [left, right]，这是一个闭区间。当 left=right 时，搜索空间不为空，仍然需要继续搜索，比如数组 arr=[66] 和 target=66，此时有 left=right=0，搜索空间为闭区间 [0, 0] ，即搜索的数组下标只有 0；如果用了 left<right，就成了半开半闭区间 [0, 0) ，此时是一个空集合，程序不能正确返回结果。

根据上面的描述内容，采用迭代的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left<=right:
        mid = left + (right-left)//2
        if arr[mid] == target:
            return mid
        elif arr[mid]>target:
            right = mid-1
        else:
            left = mid+1
    return -1

采用递归的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(arr, target, left=None, right=None):
    left = 0 if left is None else left
    right = len(arr)-1 if right is None else right
    if not arr or left>right:
        return -1
    mid = left + (right-left)//2
    if arr[mid]==target:
        return mid
    elif arr[mid]>target:
        right = mid - 1
        return binary_search(arr, target, left, right)
    else:
        left = mid + 1
        return binary_search(arr, target, left, right)

3. 寻找最左边界

我们先来看看所查找的元素在数组中的情况

mid 指向的元素刚好是 target，我们要找最左边界，那么需要查看 mid 左边是否还有 4 这个元素，缩小搜索空间为左半部分

mid 指向的元素2 小于 4，需要缩小搜索空间为右半部分

此时 mid 指向的元素刚好为 4，这是跟第一步一样，左边可能还存在元素 4，我们缩小搜索空间为左半部分

此时 right < left，跳出循环体，left 指向的即为所查找目标的最左边界

我们再看看查找的目标值不在数组中的情况

两个示例中，目标值均大于 4，缩小搜索空间为右半部分

示例 1 中 14 大于目标值 6，缩小搜索空间为左半部分；示例 2 中 14 小于目标值 30，继续缩小搜索空间为右半部分

两个示例中 mid 指针所指元素均小于目标值，缩小搜索空间为右半部分

缩小搜索空间后，两个示例均有 right<left ，结束循环。此时示例 1 的 left 指向的元素不为 6，而示例 2 的 left 超出数组边界

二分查找的一个应用是寻找满足条件的最左边界，如果不存在则返回-1，上图的查找流程，可用文字描述为：

  • 首先对 left 和 right 进行初始化 ，其中 left=0 ，right=len(arr)-1；

  • 首先对 left 和 right 进行初始化 ，其中 left=0 ，right=len(arr)-1；

  • 进入二分查找的循环体中，结束循环的条件为 left<=right；

    • 计算 mid，mid=left+(right-left)//2；
    • 判断 arr[mid] 和目标值的大小关系，因为我们要找的是最左边界，如果相等，mid 的左边可能依然存在我们的目标值，我们可以缩小搜索空间为 [left, mid-1]，即令 right=mid-1；
    • 如果 arr[mid] 大于目标值，可以缩小搜索空间为 [left, mid-1] ，即令 right=mid-1；
    • 如果 arr[mid] 小于目标值，可以缩小搜索空间为 [mid+1, right]，即令 left=mid+1；
    • 如果满足循环的条件，则不断重复此过程。
  • 结束循环，如果没有找到目标值，返回 -1；
  • 如果找到目标值，返回 left 即为最左边界。

根据上面的描述内容，采用迭代的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
def binary_search_left(arr, target):
    left, right = 0, len(arr)-1
    while left<=right:
        mid = left + (right - left)//2
        if arr[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    if left>len(arr) or arr[left]!=target:
        return -1
    return left

采用递归的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search_left(arr, target, left=None, right=None):
    left = 0 if left is None else left
    right = len(arr)-1 if right is None else right
    mid = left + (right-left)//2
    if not arr or left>len(arr):
        return -1
    if left>right and arr[left]!=target:
        return -1
    if left>right and arr[left]==target:
        return left
    if arr[mid] >= target:
        right = mid - 1
        return binary_search_left(arr, target, left, right)
    else:
        left = mid + 1
        return binary_search_left(arr, target, left, right)

4. 寻找最右边界

我们先来看看所查找的元素在数组中的情况

mid 指向的目标值刚好为 4，我们要找的是最右边界，因此需要寻找 mid 右边是否还有 4，缩小搜索空间为右半部分

mid 指向的元素是 14，大于查找目标4，因此缩小搜索空间为左半部分

此时 mid 指向的元素刚好是 4，跟第一步一样，我们要查找 mid 右边是否还有元素 4，缩小搜索空间为右半部分

此时 right<left，循环结束，right 指向的是查找目标的最右边界

我们再看看查找目标不在数组中的情况

示例 1 中目标值 6 大于 4，缩小搜索空间为右半部分；示例 2 中目标值 1 小于 4，缩小搜索空间为左半部分

示例 1 中目标值 6 小于 14，缩小搜索空间为左半部分；示例 2 中目标值 1 小于2，缩小搜索空间为左边部分

示例 1 中目标值 6 大于 14，搜小搜索空间为右半部分；示例 2 中 right < 0 < left，循环结束

示例 1 中 right<left，循环结束，且 right 指向的元素不是目标值

二分查找的另一个应用是寻找满足条件的最右边界，如果不存在则返回-1，上图的查找流程，可用文字描述为：

  • 首先对 left 和 right 进行初始化 ，其中 left=0 ，right=len(arr)-1；

  • 进入二分查找的循环体中，结束循环的条件为 left<=right；

    • 计算 mid，mid=left+(right-left)//2；
    • 判断 arr[mid] 和目标值的大小关系，因为我们要找的是最左边界，如果相等，mid 的右边可能依然存在我们的目标值，我们可以缩小搜索空间为 [mid+1, right]，即令 left=mid+1；
    • 如果 arr[mid] 大于目标值，可以缩小搜索空间为 [left, mid-1] ，即令 right=mid-1；
    • 如果 arr[mid] 小于目标值，可以缩小搜索空间为 [mid+1, right]，即令 left=mid+1；
    • 如果满足循环的条件，则不断重复此过程。
  • 结束循环，如果没有找到目标值，返回 -1；
  • 如果找到目标值，返回 right 即为最右边界。

根据上面的描述内容，采用迭代的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
def binary_search_right(arr, target):
    left, right = 0, len(arr)-1
    while left<=right:
        mid = left + (right-left)//2
        if arr[mid]<=target:
            left = mid + 1
        else:
            right = mid - 1
    if right<0 or arr[right]!=target:
        return -1
    return right

采用递归的方式实现，python 代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search_right(arr, target, left=None, right=None):
    left = 0 if left is None else left
    right = len(arr)-1 if right is None else right
    mid = left + (right-left)//2
    if not arr or right<0:
        return -1
    if left>right and arr[right]!=target:
        return -1
    if left>right and arr[right]==target:
        return right
    if arr[mid]<=target:
        left = mid + 1
        return binary_search_right(arr, target, left, right)
    else:
        right = mid - 1
        return binary_search_right(arr, target, left, right)