二分查找

发表于 更新于 分类于 ，

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 指向的即为所查找目标的最左边界

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

  • 首先对 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)