09 · 查找与字符串算法（Searching & String Algorithms）

📅 预计 90 分钟　|　⭐ 本章主题：数据里快速「找」，文本里高效「配」——从逐个翻到跳着翻

9.0 从通讯录说起

老式纸质通讯录没有索引，找人要一页页翻——这是顺序查找。按拼音首字母分好了字母卡，一下翻到那一块，再在里面扫——这是二分查找的思路。再后来有了「查号台」：给你名字，直接定位到电话，不管通讯录多大都几乎瞬间——这是哈希表。

字符串的世界同样如此：在一篇文章里找某个词，最笨的办法是每个位置都对齐比一比（朴素匹配），聪明一点则「失败后往右多跳几步」（KMP）。本章把「查找」和「字符串匹配」两件事的系统方法讲透。

9.1 顺序查找

从头到尾翻一遍

顺序查找（linear search）：从第一个元素开始挨个比，找到就返回下标，找不到返回 -1。无任何前提要求，但最坏要比较 n 次。

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

print(linear_search([3, 1, 4, 1, 5], 4))    # 输出: 2
print(linear_search([3, 1, 4, 1, 5], 9))    # 输出: -1

复杂度：平均 O(n)，最坏 O(n)，最好 O(1)（第一个就中）。什么时候用它？数据无序、规模小、只查一次。它存在的意义不是快，而是零前提——任何数据都能查。

⚠️ 常见错误

返回的是「有没有」而不是下标：题目要下标你却返回 True/False，或反之。先看清楚要求。
空列表处理：空列表直接返回 -1，别写成越界访问。
复杂对象比较：数组里是对象/字典时，== 比较的语义要符合题目（通常比较某个字段）。

9.2 二分查找 ⭐

每次砍掉一半

二分查找（binary search）的前提：数据已排序。每次取中间元素与目标比：相等则命中；比目标小，说明目标只可能在右半；比目标大，只在左半。每轮区间减半，log₂n 轮结束。

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

print(binary_search([1, 3, 5, 7, 9], 7))   # 输出: 3
print(binary_search([1, 3, 5, 7, 9], 4))   # 输出: -1

复杂度 O(log n)，秒杀顺序查找。但必须有序——如果数据无序，要么先排序（O(n log n)），要么用哈希。

边界条件是二分查找的翻车重灾区，背下这套：「区间 [left, right]，当 left <= right 时循环；mid 落在区间内；根据比较结果把左/右边界设为 mid ± 1」。用 mid + 1 / mid - 1 而不是 mid，是为了保证区间严格缩小，否则可能死循环。

二分查找不只是「找值」：还能求「第一个 ≥ target 的位置」「最后一个 ≤ target 的位置」等变体（lower_bound / upper_bound），原理一样，只是等号时收缩哪边不同。

def lower_bound(arr, target):
    """第一个 >= target 的下标；没有则返回 len(arr)"""
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

print(lower_bound([1, 3, 3, 5, 7], 3))   # 输出: 1
print(lower_bound([1, 3, 3, 5, 7], 4))   # 输出: 3

⚠️ 常见错误

忘了数据必须有序：无序数据直接二分，结果完全随机。
循环条件写错：left <= right 与 left < right 对应不同写法；left < right 时区间取 [left, right)，初始化 right = len(arr)。
mid ± 1 忘写 ± 1：写成 left = mid 会在死循环边缘徘徊（尤其区间长为 2 时）。
mid 溢出：Python 无此问题；其他语言习惯写成 left + (right - left) // 2。
lower_bound / upper_bound 语义混淆：题目要「第一个 ≥」还是「最后一个 <」，收缩方向不同。

9.3 哈希表与哈希冲突 ⭐

查号台：O(1) 定位

哈希表（hash table）用一个哈希函数（hash function）把键映射成数组下标，把「找键」变成「直接算下标」，平均 O(1)。Python 的字典和集合底层就是哈希表。

# 用 Python 的 dict 体会哈希的 O(1) 查找
phone = {}
phone["小明"] = "138"
phone["小红"] = "139"
print(phone["小明"])              # 138，按键直达，跟 dict 有多大无关
print(len(phone))                 # 2

但「不同键算出同一个下标」完全可能发生，这就是哈希冲突（collision）。两种主流解决法：

链地址法（chaining）：每个下标挂一个链表，冲突就挂到链上，查找时先定位桶再遍历链表。字典里一个桶一般只有几个元素，所以仍接近 O(1)。

class HashTable:
    def __init__(self, size=7):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size        # 取模定桶

    def set(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):   # 键已存在 → 更新
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))           # 不存在 → 链上追加

    def get(self, key):
        bucket = self.buckets[self._hash(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

h = HashTable(7)
h.set("apple", 3)
h.set("banana", 5)
print(h.get("apple"))      # 输出: 3
print(h.get("banana"))     # 输出: 5

开放定址法（open addressing）：冲突时按某种探测序列（如线性探测：+1、+2…）找下一个空位。不额外用链表，但表快满时性能骤降，需要扩容（resize，通常翻倍）。

装填因子（load factor）= 元素数 / 桶数。链地址法一般控制在 0.75 左右就扩容，保证平均桶长小。哈希函数设计得好，冲突少，接近 O(1)；设计差（都挤到一个桶），退化回 O(n)。

Python 里怎么用：真正常用的是内置 dict / set；in 判断、setdefault、Counter 都是哈希表的现成工具。刷题时「数出现次数」「查重」「两数之和」几乎都靠它。

from collections import Counter

print(Counter("algorithm"))   # 输出: Counter({'a': 1, 'l': 1, 'g': 1, ...})
print(1 in {1, 2, 3})         # 输出: True    集合查重是 O(1)

⚠️ 常见错误

键必须可哈希：列表、字典不能当键（可变 → 哈希值会变）；要存可变键先用元组包起来。
哈希函数取模负数：Python 的 % 结果非负，别的语言可能得负数下标，需 (hash(key) % size + size) % size。
装填因子过高不扩容：自建哈希表时会退化；生产环境用内置 dict 即可，别自造。
把「平均 O(1)」当「绝对 O(1)」：最坏情况（全冲突）仍是 O(n)，题目问最坏复杂度要答 O(n)。

9.4 查找结构对比

结构	前提	平均查找	最坏	适用
顺序查找	无	O(n)	O(n)	无序小数据
二分查找	有序	O(log n)	O(log n)	有序静态数据
哈希表	键可哈希	O(1)	O(n)	快速精确查找、去重、计数
二叉搜索树	可比较	O(log n)	O(n)	需要动态增删 + 有序遍历

记忆：要快、不关心顺序 → 哈希；要顺序遍历/范围查询 → 树；数据有序且只查 → 二分。Python 里 dict/set 是哈希，bisect 模块是现成二分。

⚠️ 常见错误

哈希和排序混用：哈希表天生无序，for k in dict 的顺序（插入序）不等于排序序，要排序结果必须 sorted()。
二分前提遗忘：有序数组才能二分；哈希表则要求键可哈希，两者前提不同。
只记平均不记最坏：复杂度讨论要分平均/最坏，哈希最坏是 O(n)。

9.5 朴素字符串匹配

每个位置对齐，逐个字符比

朴素匹配（naive matching）：让模式串在文本的每个起始位置对齐一次，逐字符比较。文本长 n、模式长 m，最坏 O(n·m)（比如文本全是 a、模式是 a…b）。

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    positions = []
    for i in range(n - m + 1):          # 只可能出现在这些起点
        if text[i:i + m] == pattern:
            positions.append(i)
    return positions

print(naive_search("ABABCABAB", "ABAB"))
# 输出: [0, 5]    在位置 0 和 5 各匹配到一次
print(naive_search("hello", "xyz"))
# 输出: []

这版用切片比较，简洁清晰。若要知道「在第 i 位匹配失败时，公共前缀有多长」，就得学下一节的 KMP。

⚠️ 常见错误

循环上界越界：range(n - m + 1) 别写成 range(n)，否则 text[i:i+m] 会拿到短串误判。
空模式串：m=0 时，n - m + 1 = n + 1，需要特殊处理（通常返回所有位置或空）。
重叠匹配：题目允许重叠（如 "AAAA" 里找 "AA"）时朴素写法天然支持；要求不重叠需手动推进 i。

9.6 KMP 思想：失败后不从头来 ⭐

借「最长相等前后缀」跳着走

朴素匹配的浪费在于：在某位失败后，模式串从头对齐、文本指针只前进 1，之前比过的信息全丢了。KMP（Knuth-Morris-Pratt）的思路是：失败时，根据模式串自身「已匹配前缀」的重复结构，让模式串往右滑一段，而不是回退到 0。

滑多远的依据是 next 数组（也叫 prefix function / 失配函数）：

next[i] = pattern[:i+1]（前缀）的最长相等前后缀长度。
例："ABAB" 的 next = [0, 0, 1, 2]——"ABA" 的最长相等前后缀是 "A"（长度 1），"ABAB" 的是 "AB"（长度 2）。

def build_next(pattern):
    nxt = [0] * len(pattern)
    j = 0                                    # j = 当前已匹配的前缀长度
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = nxt[j - 1]                   # 回退到上一个可用的前缀长度
        if pattern[i] == pattern[j]:
            j += 1
        nxt[i] = j
    return nxt

def kmp_search(text, pattern):
    if not pattern:
        return []
    nxt = build_next(pattern)
    j = 0
    positions = []
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:    # 失配：不回退 i，只滑动模式串
            j = nxt[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):                # 完整匹配一次
            positions.append(i - j + 1)
            j = nxt[j - 1]                   # 继续找下一个匹配
    return positions

print(build_next("ABAB"))
# 输出: [0, 0, 1, 2]
print(kmp_search("ABABCABAB", "ABAB"))
# 输出: [0, 5]    和朴素结果一致，但文本指针从不回退

KMP 为什么是 O(n+m)：文本指针 i 只增不减；模式串指针 j 虽然会回退，但回退总量不超过前进总量，均摊下来仍是线性。这是「把已经比较过的信息复用来避免重复比较」的典型代表。

考试 / 面试要求：手推 next 数组、解释「失配时为什么滑到 nxt[j-1]」。理解核心即可：next 数组回答「失败了，模式串能往右滑多少而不错过潜在匹配」。

⚠️ 常见错误

next 数组与「前缀包含自身」混淆：最长相等前后缀的「前后缀」必须是真前缀/真后缀（不能是整串自己）。
失配回退写成 j = 0：那退化成朴素匹配；正确回退到 nxt[j - 1]。
文本指针回退：KMP 的精髓是 i 永不回退，只在 j 上做文章。
next[0] 忘了是 0：单个字符没有真前后缀，next[0] = 0。

9.7 常见字符串题套路

字符串题的大量技巧就藏在本章知识里，列四个高频套路：

① 判断回文——字符串等于它的反转：

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome("racecar"))   # 输出: True
print(is_palindrome("hello"))     # 输出: False

② 反转 / 按规则变换——切片反转、列表拼接：

def reverse_words(s):
    return " ".join(s.split()[::-1])

print(reverse_words("the sky is blue"))
# 输出: blue is sky the

③ 最长公共前缀——先取第一个词做基准，逐步缩短：

def longest_common_prefix(words):
    if not words:
        return ""
    prefix = words[0]
    for w in words[1:]:
        while not w.startswith(prefix):
            prefix = prefix[:-1]          # 缩短前缀直到能匹配
            if not prefix:
                return ""
    return prefix

print(longest_common_prefix(["flower", "flow", "flight"]))
# 输出: fl

④ 字符频次——哈希表计数，几乎万能：

def char_count(s):
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    return count

print(char_count("algorithm"))
# 输出: {'a': 1, 'l': 1, 'g': 1, 'o': 1, 'r': 1, 'i': 1, 't': 1, 'h': 1, 'm': 1}

「字符频次」是判断「两个字符串是否互为异位词」（字母构成相同）的钥匙：比较两个 Counter 是否相等即可。

from collections import Counter
print(Counter("listen") == Counter("silent"))   # 输出: True

⚠️ 常见错误

忽略大小写 / 空格：题目说「忽略空格、大小写」时，先 s.lower()、去掉非字母再判断。
切片反转 [::-1] 会新开内存：大字符串（10⁶ 级）上谨慎用；一般题目没问题。
空字符串边界：空串、单字符串在回文 / 公共前缀里都要单独想清楚返回值。

🧠 记忆口诀

查找三兄弟：无序顺序找，有序二分跳，键可哈希 O(1) 秒。
二分边界：left ≤ right 闭区间，mid 归半边 ±1。
哈希冲突：链地址挂链，开放定址找空位，装填因子高了就扩容。
KMP 一句话：文本 i 不回头，模式滑到 next。
频次统计：get(ch, 0) + 1 走天下。

⭐ 考点清单

顺序 / 二分 / 哈希的前提与复杂度对比
二分查找边界条件、lower_bound / upper_bound 变体
哈希函数、冲突解决（链地址 / 开放定址）、装填因子、可哈希
朴素匹配 O(n·m) 与切片的实现
KMP 的 next 数组手推、失配滑动、O(n+m) 为什么
字符串高频题：回文、反转、最长公共前缀、字符频次 / 异位词
Python 内置工具：dict、set、Counter、str.startswith、s[::-1]

📌 中英术语表

中文	English	说明
查找	search	在数据中定位目标
顺序查找	linear search	从头到尾挨个比较
二分查找	binary search	有序数据每次砍半
哈希表	hash table	键映射下标的查找结构
哈希函数	hash function	把键映射成下标
哈希冲突	collision	不同键映射到同一位置
链地址法	chaining	每个桶挂链表
开放定址法	open addressing	冲突后探测空位
装填因子	load factor	元素数 / 桶数
扩容	resizing	表满时扩大容量
字符串匹配	string matching	在文本中找模式串
朴素匹配	naive matching	逐位对齐比较
模式串	pattern	要找的字符串
文本串	text	被搜索的字符串
KMP 算法	Knuth-Morris-Pratt	利用 next 数组避免回退
next 数组	prefix function	最长相等前后缀长度
回文	palindrome	正反读一样
异位词	anagram	字母构成相同
最长公共前缀	longest common prefix	多个字符串的共同开头