查找算法

查找是在数据集中定位目标的过程，是数据结构与算法的核心操作。顺序查找 O(n)、二分查找 O(log n)、哈希查找 O(1)、树表查找 O(log n)，复杂度取决于底层组织方式。掌握二分查找的边界写法是面试高频考点。

顺序查找

从头到尾逐个比较，不要求数据有序，适合小规模或无序数据：

def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1
print(linear_search([5, 3, 8, 1], 8))   # 输出：2

最好 O(1)（第一个就是目标），平均与最坏都是 O(n)。

二分查找

二分查找要求数组有序：每次与中间元素比较，目标小则去左半、大则去右半，每轮砍掉一半范围。写对的关键是保持「区间定义」一致，避免死循环与漏查：

def binary_search(a, target):
    left, right = 0, len(a) - 1        # 闭区间 [left, right]
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            left = mid + 1             # 目标在右半
        else:
            right = mid - 1            # 目标在左半
    return -1                          # 未找到

a = [1, 3, 5, 7, 9]
print(binary_search(a, 7))             # 输出：3
print(binary_search(a, 6))             # 输出：-1

常见变体：查找第一个等于 target 的位置、查找最后一个小于等于 target 的位置、在旋转数组里查找，本质都是二分。

哈希查找与树表查找

• 哈希查找：通过哈希函数直接定位，平均 O(1)，适合键值精确匹配；但不支持范围查询与有序遍历。
• 树表查找：把数据组织成二叉搜索树或自平衡树（红黑树、B+ 树），查找 O(log n)，天然支持范围查询与有序输出，MySQL 索引、TreeMap 都是这类实现。

查找方式	平均时间	前提	特点
顺序查找	O(n)	无序即可	实现最简单
二分查找	O(log n)	有序数组	需支持随机访问
哈希查找	O(1)	键可哈希	仅精确匹配，无序
树表查找	O(log n)	有序结构	支持范围查询

复杂度推导要点

• 二分每轮缩小一半，n 个元素最多比较 log₂(n) 次，所以是 O(log n)。
• 顺序查找最坏要比较 n 次；哈希查找理想情况下一次定位，但冲突多会退化。
• 面试常问「有序数组 + 频繁插入怎么办」：数组插入是 O(n)，应改用平衡树或跳表，体现对数据结构的理解。

面试要点

• 高频题：二分查找边界变体、搜索旋转排序数组、求平方根、二维矩阵查找。
• 手写二分先声明区间（闭区间还是左闭右开），再让 while 条件与 mid 的加减法配套，是防错的关键。
• 哈希表时间 O(1) 的前提是哈希函数均匀且扩容及时，能补一句「最坏 O(n)」更显严谨。

小结：查找效率由数据结构决定：无序用顺序、有序用二分、键值用哈希、动态有序用树表；熟记二分模板与四种查找的复杂度，查找题就尽在掌握。