二分查找

简介

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

时间复杂度：$O(logn)$，在二分循环中，区间每轮缩小一半，因此循环次数为 $log_2⁡n$ 。

空间复杂度：$O(1)$

二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 $O(nlog⁡n)$ ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 $O(n)$ ，也是非常昂贵的。

问题

给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 −1 。

基本实现

Python

from typing import List


def binary_search(arr: List[int], target: int) -> int:
    i = 0  # 数组头部元素的索引
    j = len(arr) - 1  # 数组尾部元素的索引
    while i <= j:
        mid = (i + j) // 2  # 数组中间元素的索引
        if arr[mid] == target:
            return mid

        if arr[mid] > target:  # 目标值在数组中间元素的左边
            j = mid - 1
        else:  # 目标值在数组中间元素的右边
            i = mid + 1
    return -1


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 17]
    target = 10
    print(binary_search(arr, target))

Go

/* 二分查找（双闭区间） */
func binarySearch(nums []int, target int) int {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    i, j := 0, len(nums)-1
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    for i <= j {
        m := i + (j-i)/2      // 计算中点索引 m
        if nums[m] < target { // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1
        } else if nums[m] > target { // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1
        } else { // 找到目标元素，返回其索引
            return m
        }
    }
    // 未找到目标元素，返回 -1
    return -1
}

二分查找插入点

无重复元素情况

给定一个长度为 n 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引。

def binary_search_insertion_simple(nums: list[int], target: int) -> int:
    """二分查找插入点（无重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            return m  # 找到 target ，返回插入点 m
    # 未找到 target ，返回插入点 i
    return i


"""Driver Code"""
if __name__ == "__main__":
    # 无重复元素的数组
    nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]
    # 二分查找插入点
    target = 6
    index = binary_search_insertion_simple(nums, target)
    print(f"元素 {target} 的插入点的索引为 {index}")

存在重复元素的情况

假设数组中存在多个 target ，则普通二分查找只能返回其中一个 target 的索引，而无法确定该元素的左边和右边还有多少 target。

整体流程保持不变，每轮先计算中点索引 m ，再判断 target 和 nums[m] 的大小关系，分为以下几种情况。

• 当 nums[m] < target 或 nums[m] > target 时，说明还没有找到 target ，因此采用普通二分查找的缩小区间操作，从而使指针 i 和 j 向 target 靠近。
• 当 nums[m] == target 时，说明小于 target 的元素在区间 $[i,m−1]$ 中，因此采用 $j=m−1$ 来缩小区间，从而使指针 j 向小于 target 的元素靠近。

循环完成后，i 指向最左边的 target ，j 指向首个小于 target 的元素，因此索引 i 就是插入点。

def binary_search_insertion(nums: list[int], target: int) -> int:
    """二分查找插入点（存在重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            j = m - 1  # 首个小于 target 的元素在区间 [i, m-1] 中
    # 返回插入点 i
    return i


"""Driver Code"""
if __name__ == "__main__":
    # 包含重复元素的数组
    nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]
    # 二分查找插入点
    target = 6
    index = binary_search_insertion(nums, target)
    print(f"元素 {target} 的插入点的索引为 {index}")