第 7 章 · 查找

查找 = 给定键快速定位记录；核心矛盾：顺序慢、哈希快但要额外空间。

7.1 顺序查找 vs 二分查找

// 顺序查找 O(n)：无需有序
int seq(int *a, int n, int k) { for (int i = 0; i < n; i++) if (a[i] == k) return i; return -1; }

// 二分查找 O(log n)：要求有序，反复对半收缩区间
int bsearch(int *a, int n, int k) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // 防 lo+hi 溢出
        if (a[mid] == k) return mid;
        else if (a[mid] < k) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

二分每次排除一半，是 O(log n) 阶的典型（第 1 章）。但前提是有序且支持随机访问——链表无法二分。

7.2 哈希表：键 → 下标

哈希函数把键映射到桶下标，理想下 O(1)。两个关键：哈希函数构造 + 冲突处理。

• 除留余数法：h(k) = k % m，m 取素数减少规律性冲突。
• 冲突不可避免（鸽巢原理），两种处理策略见下。

7.3 冲突处理：开放定址 vs 链地址

// 链地址法：每个桶挂一条链表（第 2 章）
#define M 1000
typedef struct Node { int key, val; struct Node *next; } Node;
Node *bucket[M];

void put(int key, int val) {
    int i = key % M;
    Node *n = malloc(sizeof(*n));
    if (!n) return;
    n->key = key; n->val = val; n->next = bucket[i];
    bucket[i] = n;
}

// 开放定址（线性探测）：冲突就往后找空位
#define EMPTY (-1)
int find_slot(int *t, int m, int key) {
    int i = key % m;
    while (t[i] != EMPTY && t[i] != key) i = (i + 1) % m;
    return i;   // 返回空位或 key 已存在的位置
}

	开放定址	链地址
存储	数组内探测	数组 + 链表
删除	需墓碑标记	直接摘链
装载因子	需 < 0.7，否则性能骤降	可 > 1
缓存	连续，友好	链表离散

7.4 查找性能分析

• 顺序查找平均 O(n)；二分 O(log n) 但需排序一次 O(n log n)（第 8 章）。
• 哈希平均 O(1)，最坏 O(n)（全部冲突成一条链）。装载因子 α = 元素数/桶数，α 越大冲突越多；链地址平均查找长度约 1 + α/2。

对比：顺序 vs 二分 vs 哈希——

方法	预处理	单次查找	额外空间	约束
顺序	无	O(n)	无	无
二分	排序 O(n log n)	O(log n)	无	有序 + 随机访问
哈希	建表 O(n)	平均 O(1)	O(n)	需好哈希函数

数据只查一次用顺序；频繁查找且可排序用二分；键值频繁增删查用哈希。

对比：开放定址省指针、缓存友好，但删除麻烦、装载因子受限；链地址实现简单、可高装载，但指针开销 + 缓存不友好。