查找与二分

第 13 章 · 数据结构与算法

一、线性查找

在长度为 n 的序列中找目标值，若不保证有序，只能顺序扫描，最坏比较 n 次，O(n)。若找到则返回下标，否则返回 -1 或插入位置。线性查找也用于找最大值、最小值、满足条件的第一个元素等。

from typing import List


def linear_search(arr: List[int], target: int) -> int:
    """线性查找：返回 target 的下标，不存在返回 -1。"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

二、二分查找的前提与基本写法

前提：序列有序（或具有某种单调性），才能根据「中间值与目标的大小关系」排除一半。区间约定：常用左闭右开 [left, right)，即有效下标为 left..right-1；循环条件为 left < right，缩区间时 right = mid 或 left = mid + 1，避免死循环。mid 防溢出：mid = left + (right - left) // 2。

from typing import List


def binary_search(arr: List[int], target: int) -> int:
    """
    标准二分查找：有序数组中找到 target 的下标，不存在返回 -1。
    左闭右开 [left, right)，mid = left + (right - left) // 2。
    """
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

三、二分查找变体

第一个等于 target：当 arr[mid] == target 时不要立刻返回，令 right = mid 继续往左找；最后 left 为「第一个等于」的下标（若不存在则 left 为第一个大于 target 的下标）。最后一个等于 target：相等时令 left = mid + 1 往右挤，最后 left - 1 或 right - 1 为「最后一个等于」。第一个 ≥ target（lower_bound）：比较时 arr[mid] < target 则 left = mid + 1，否则 right = mid；退出时 left 即为第一个 ≥ target 的位置。最后一个 ≤ target：可转化为「第一个 > target」减 1，或对称写。这些变体的循环不变式要一致，避免边界错误。

from typing import List


def lower_bound(arr: List[int], target: int) -> int:
    """
    第一个 >= target 的下标；若都 < target 则返回 len(arr)。
    左闭右开，arr[mid] < target 则 left = mid+1，否则 right = mid。
    """
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left


def upper_bound(arr: List[int], target: int) -> int:
    """
    第一个 > target 的下标；若都 <= target 则返回 len(arr)。
    """
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left


def search_range(arr: List[int], target: int) -> List[int]:
    """返回 target 的起始与结束下标 [start, end]，不存在则 [-1, -1]。"""
    lo = lower_bound(arr, target)
    if lo == len(arr) or arr[lo] != target:
        return [-1, -1]
    hi = upper_bound(arr, target) - 1
    return [lo, hi]

四、搜索插入位置

在有序数组中找 target 的插入位置，使插入后仍有序。即第一个 ≥ target 的下标，即 lower_bound。若 target 已存在，插入在其左侧或右侧依题意；通常理解为「第一个 ≥ target」则插入在相同元素最左侧。

五、旋转数组与答案二分

旋转数组：有序数组 [a0, a1, …, an-1] 从某处截断并前后对调，如 [4,5,6,7,0,1,2]。仍可二分：mid 与某侧（如 right）比较，判断 mid 在「前半段」还是「后半段」，再判断 target 在 mid 左还是右。答案二分：若「答案 x 满足条件」具有单调性（如 x 可行则比 x 更大/更小也可行），可二分答案，再在 O(f(n)) 内检查是否可行，总时间 O(f(n) log 范围)。典型：x 的平方根、满足条件的最小/最大值。

from typing import List


def search_rotated(arr: List[int], target: int) -> int:
    """
    旋转排序数组（无重复）中找 target。比较 nums[mid] 与 nums[right] 判断 mid 在左半还是右半，
    再判断 target 在 mid 左还是右。
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] <= arr[right]:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return -1

六、小结

线性查找 O(n)，适用于无序。二分查找要求有序，左闭右开、mid 防溢出，O(log n)。变体：lower_bound（第一个 ≥）、upper_bound（第一个 >）、search_range。旋转数组通过 mid 与端点比较判断所在段再二分。答案二分在单调性下二分答案再检查。下一章讲递归与分治。

七、例题

以下例题使用 Python 3 类型标注与注释。

from typing import List


def search_insert(nums: List[int], target: int) -> int:
    """第一个 >= target 的下标，即 lower_bound。"""
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

from typing import List


def search_rotated_sorted(nums: List[int], target: int) -> int:
    """
    nums[mid] 与 nums[right] 比较：若 nums[mid] <= nums[right]，则 [mid, right] 有序；
    否则 [left, mid] 有序。在有序的那半里判断 target 是否在范围内，缩区间。
    """
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] <= nums[right]:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return -1

def my_sqrt(x: int) -> int:
    """
    二分答案：找最大的 k 使得 k*k <= x。左闭右开，mid*mid <= x 则 left = mid+1 尝试更大，否则 right = mid。
    返回 left - 1（最后一个满足 k*k <= x 的 k）。
    """
    if x <= 1:
        return x
    left, right = 0, x + 1
    while left < right:
        mid = left + (right - left) // 2
        if mid * mid <= x:
            left = mid + 1
        else:
            right = mid
    return left - 1

from typing import List


def search_range(nums: List[int], target: int) -> List[int]:
    """lower_bound 得第一个 >= target；upper_bound 得第一个 > target，则 [lo, hi-1] 为范围。"""
    def lower_bound(t: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < t:
                lo = mid + 1
            else:
                hi = mid
        return lo

    lo = lower_bound(target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    hi = lower_bound(target + 1) - 1  # 第一个 > target 的前一个即最后一个 == target
    return [lo, hi]