# 19. 查找 ## 概念 查找是在数据结构中定位「关键字等于给定值」的元素的过程。核心衡量指标是**平均查找长度（ASL，Average Search Length）**：查找过程中关键字的**平均比较次数**。查找算法按是否需要事先组织数据，可分为以下几类： **1. 顺序查找（线性查找）** - 从头到尾逐个比较。对**无序表**或**顺序表**、**链表**均适用，是最通用但最慢的方法。 - 无序表成功查找 ASL = (n+1)/2，失败查找 ASL = n。 - 若表**有序**，失败时不必查完整个表（遇到比关键字大/小的元素即可停），失败 ASL 降为约 n/2。 **2. 折半查找（二分查找）** - 只适用于**有序**且**顺序存储**（数组）的线性表。每次与中间元素比较，排除一半区间，不断缩小范围。 - ASL = O(log n)。因为比较过程构成一棵「判定树」，查找次数不超过树高 ⌈log₂(n+1)⌉。 - 注意：链表无法随机访问中间元素，因此二分不适用于链表。 **3. 分块查找（索引顺序查找）** - 数据分成若干**块**，块内无序、块间有序；另建一张**索引表**记录每块的最大关键字和起始位置。 - 先在索引表上二分（或顺序）找到所在块 O(log m)，再在块内顺序查找 O(n/m)。ASL ≈ log₂(m+1) + (n/m+1)/2。 - 折中方案：比顺序快，又不像二分那样要求整表有序。 **4. 哈希查找（散列查找）** - 通过**哈希函数** `h(key)` 把关键字直接映射为存储地址，期望 O(1) 找到。 - **冲突**不可避免（不同关键字映射到同一地址）。处理冲突的常用方法： - **开放定址法**：冲突后探测下一个空位。线性探测（依次 +1，易产生堆积）、二次探测（±1²、±2²…）。 - **链地址法（拉链法）**：每个哈希地址挂一条链表，冲突元素都挂到同一条链上（本页语言实现采用此法）。 - **负载因子 α = 表中元素数 / 表长**。α 越大冲突越严重。链地址法下成功查找 ASL ≈ 1 + α/2，失败 ≈ α；α 较小时哈希接近 O(1)。 - 各种查找方法优劣对比： | 方法 | 优点 | 缺点 | 适用场景 | | -------- | ---------------------- | ---------------------------- | ------------------------ | | 顺序查找 | 实现简单，任意存储结构 | 太慢 | 小规模、无序数据 | | 折半查找 | 快，O(log n) | 要求有序 + 顺序存储 | 静态有序表、频繁查找 | | 分块查找 | 插入删除灵活，速度适中 | 需维护索引表 | 动态插入较多、块间有序 | | 哈希查找 | 平均 O(1)，最快 | 冲突处理复杂、不支持有序遍历 | 关键字集合大、仅按值查询 | ## 核心操作 / 算法 1. **顺序查找**：`for i in 0..n-1: if a[i]==key return i`。 2. **折半查找**（迭代版）：`lo=0, hi=n-1`，`mid = lo+(hi-lo)/2`；`a[mid]==key` 命中，`a[mid]hi` 时失败。 3. **折半查找**（递归版）：递归边界 `lo>hi`，中间位置判定后向一半区间递归。 4. **分块查找**：先在索引表定位块，再在块内顺序查找。 5. **哈希查找（链地址法）**：`hash(key) = key % size` 定位桶，在该桶链表内顺序比较。 6. 平均查找长度 ASL 的计算：成功/失败查找的比较次数与对应概率的加权平均。 ## 复杂度分析 | 算法 | 时间复杂度 | 空间复杂度 | 前提条件 | | -------------------- | --------------------- | ------------------------------ | --------------------------- | | 顺序查找（无序） | O(n) | O(1) | 无 | | 顺序查找（有序） | O(n)，失败时约 O(n/2) | O(1) | 数据有序 | | 折半查找 | O(log n) | 迭代 O(1)，递归 O(log n)（栈） | 有序 + 顺序存储 | | 分块查找 | O(log m + n/m) | O(m)（索引表） | 块间有序 | | 哈希查找（链地址法） | 平均 O(1)，最坏 O(n) | O(n) | 好的散列函数 + 合理负载因子 | 说明：哈希最坏 O(n) 发生在所有关键字全部冲突到同一条链上；工程上通过控制负载因子（如 α ≤ 0.75）和随机化散列函数把概率压到几乎为零。 ## 语言实现 以下四种实现完全等价，每个文件包含两部分演示： 1. **折半查找**：同一有序数组，给出**迭代**与**递归**两种实现； 2. **哈希查找**：用**链地址法**处理冲突，插入关键字 `15, 25, 35, 7, 17, 27, 3, 13`（对 10 取模后多处冲突，便于观察冲突处理），再查找命中与未命中元素并打印比较次数。 ### C ```c #include #include /* ---------- 折半查找（二分） ---------- */ // 迭代版：在有序数组 a[0..n-1] 中查找 key，返回下标，找不到返回 -1 int binarySearchIterative(int a[], int n, int key) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // 防溢出写法 if (a[mid] == key) return mid; else if (a[mid] < key) lo = mid + 1; // 去右半区 else hi = mid - 1; // 去左半区 } return -1; } // 递归版 int binarySearchRecursive(int a[], int lo, int hi, int key) { if (lo > hi) return -1; // 递归边界：区间为空 int mid = lo + (hi - lo) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) return binarySearchRecursive(a, mid + 1, hi, key); else return binarySearchRecursive(a, lo, mid - 1, key); } /* ---------- 哈希查找（链地址法） ---------- */ #define TABLE_SIZE 10 // 哈希结点：每个桶是一条单链表 typedef struct Node { int key; struct Node *next; } Node; typedef struct { Node *buckets[TABLE_SIZE]; } HashTable; // 哈希函数：除留余数法 int hash(int key) { return (key >= 0 ? key : -key) % TABLE_SIZE; } // 初始化：所有桶置空 void hashInit(HashTable *ht) { for (int i = 0; i < TABLE_SIZE; i++) ht->buckets[i] = NULL; } // 插入关键字：冲突时头插到对应桶的链表上 void hashInsert(HashTable *ht, int key) { int idx = hash(key); Node *p = ht->buckets[idx]; while (p) { if (p->key == key) return; // 已存在，不重复插入 p = p->next; } Node *node = (Node *)malloc(sizeof(Node)); node->key = key; node->next = ht->buckets[idx]; // 头插 ht->buckets[idx] = node; } // 查找关键字，返回是否命中并打印比较次数 int hashSearch(HashTable *ht, int key) { int idx = hash(key); Node *p = ht->buckets[idx]; int compare = 0; while (p) { compare++; if (p->key == key) { printf(" 查找 %d 成功，比较次数 = %d\n", key, compare); return 1; } p = p->next; } printf(" 查找 %d 失败，比较次数 = %d\n", key, compare); return 0; } // 释放哈希表内存 void hashDestroy(HashTable *ht) { for (int i = 0; i < TABLE_SIZE; i++) { Node *p = ht->buckets[i]; while (p) { Node *tmp = p; p = p->next; free(tmp); } } } int main() { /* 折半查找演示 */ int a[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int n = sizeof(a) / sizeof(a[0]); int key = 7; printf("迭代版: %d 的下标 = %d\n", key, binarySearchIterative(a, n, key)); printf("递归版: %d 的下标 = %d\n", key, binarySearchRecursive(a, 0, n - 1, key)); /* 哈希查找演示：15、25、35 取模同为 5，7、17、27 同为 7，3、13 同为 3 */ HashTable ht; hashInit(&ht); int keys[] = {15, 25, 35, 7, 17, 27, 3, 13}; int m = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < m; i++) hashInsert(&ht, keys[i]); printf("\n哈希表查找：\n"); hashSearch(&ht, 25); // 命中 hashSearch(&ht, 99); // 未命中 hashDestroy(&ht); return 0; } ``` ### C++ ```C++ #include #include #include using namespace std; /* ---------- 折半查找（二分） ---------- */ // 迭代版 int binarySearchIterative(const vector& a, int key) { int lo = 0, hi = (int)a.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) lo = mid + 1; else hi = mid - 1; } return -1; } // 递归版 int binarySearchRecursive(const vector& a, int lo, int hi, int key) { if (lo > hi) return -1; // 递归边界 int mid = lo + (hi - lo) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) return binarySearchRecursive(a, mid + 1, hi, key); else return binarySearchRecursive(a, lo, mid - 1, key); } /* ---------- 哈希查找（链地址法） ---------- */ class HashTable { private: vector> buckets; // 每个桶是一条链表 int size; // 除留余数法（兼容负数） int hash(int key) const { return (key % size + size) % size; } public: HashTable(int s) : buckets(s), size(s) {} void insert(int key) { int idx = hash(key); for (int v : buckets[idx]) if (v == key) return; // 已存在 buckets[idx].push_front(key); // 头插 } bool search(int key) const { int idx = hash(key); int compare = 0; for (int v : buckets[idx]) { compare++; if (v == key) { cout << " 查找 " << key << " 成功，比较次数 = " << compare << endl; return true; } } cout << " 查找 " << key << " 失败，比较次数 = " << compare << endl; return false; } }; int main() { /* 折半查找演示 */ vector a = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int key = 7; cout << "迭代版: " << key << " 的下标 = " << binarySearchIterative(a, key) << endl; cout << "递归版: " << key << " 的下标 = " << binarySearchRecursive(a, 0, (int)a.size() - 1, key) << endl; /* 哈希查找演示 */ HashTable ht(10); int keys[] = {15, 25, 35, 7, 17, 27, 3, 13}; for (int k : keys) ht.insert(k); cout << "\n哈希表查找：" << endl; ht.search(25); // 命中 ht.search(99); // 未命中 return 0; } ``` ### Java ```java import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class SearchDemo { /* ---------- 折半查找（二分） ---------- */ // 迭代版 static int binarySearchIterative(int[] a, int key) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) lo = mid + 1; else hi = mid - 1; } return -1; } // 递归版 static int binarySearchRecursive(int[] a, int lo, int hi, int key) { if (lo > hi) return -1; // 递归边界 int mid = lo + (hi - lo) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) return binarySearchRecursive(a, mid + 1, hi, key); else return binarySearchRecursive(a, lo, mid - 1, key); } /* ---------- 哈希查找（链地址法） ---------- */ static class HashTable { private List> buckets; // 每个桶是一条链表 private int size; HashTable(int s) { size = s; buckets = new ArrayList<>(s); for (int i = 0; i < s; i++) buckets.add(new LinkedList<>()); } // 除留余数法（Java 取模可能为负，先取余再修正） private int hash(int key) { return ((key % size) + size) % size; } void insert(int key) { int idx = hash(key); LinkedList list = buckets.get(idx); if (list.contains(key)) return; // 已存在 list.addFirst(key); // 头插 } boolean search(int key) { int idx = hash(key); int compare = 0; for (int v : buckets.get(idx)) { compare++; if (v == key) { System.out.println(" 查找 " + key + " 成功，比较次数 = " + compare); return true; } } System.out.println(" 查找 " + key + " 失败，比较次数 = " + compare); return false; } } public static void main(String[] args) { /* 折半查找演示 */ int[] a = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int key = 7; System.out.println("迭代版: " + key + " 的下标 = " + binarySearchIterative(a, key)); System.out.println("递归版: " + key + " 的下标 = " + binarySearchRecursive(a, 0, a.length - 1, key)); /* 哈希查找演示 */ HashTable ht = new HashTable(10); int[] keys = {15, 25, 35, 7, 17, 27, 3, 13}; for (int k : keys) ht.insert(k); System.out.println("\n哈希表查找："); ht.search(25); // 命中 ht.search(99); // 未命中 } } ``` ### Python ```python """折半查找（二分）与哈希查找（链地址法）演示""" # ---------- 折半查找 ---------- def binary_search_iterative(a, key): """迭代版二分查找，返回下标，找不到返回 -1""" lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] == key: return mid elif a[mid] < key: lo = mid + 1 else: hi = mid - 1 return -1 def binary_search_recursive(a, lo, hi, key): """递归版二分查找""" if lo > hi: return -1 # 递归边界：区间为空 mid = lo + (hi - lo) // 2 if a[mid] == key: return mid elif a[mid] < key: return binary_search_recursive(a, mid + 1, hi, key) else: return binary_search_recursive(a, lo, mid - 1, key) # ---------- 哈希查找（链地址法） ---------- class HashTable: """链地址法哈希表：每个桶是一条链表（用 list 模拟）""" def __init__(self, size): self.size = size self.buckets = [[] for _ in range(size)] def _hash(self, key): return key % self.size # 除留余数法 def insert(self, key): idx = self._hash(key) if key not in self.buckets[idx]: # 冲突时挂到同一条链上 self.buckets[idx].append(key) def search(self, key): idx = self._hash(key) compare = 0 for v in self.buckets[idx]: compare += 1 if v == key: print(f" 查找 {key} 成功，比较次数 = {compare}") return True print(f" 查找 {key} 失败，比较次数 = {compare}") return False if __name__ == "__main__": # 折半查找 a = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] key = 7 print(f"迭代版: {key} 的下标 = {binary_search_iterative(a, key)}") print(f"递归版: {key} 的下标 = {binary_search_recursive(a, 0, len(a) - 1, key)}") # 哈希查找 ht = HashTable(10) for k in [15, 25, 35, 7, 17, 27, 3, 13]: ht.insert(k) print("\n哈希表查找：") ht.search(25) # 命中 ht.search(99) # 未命中 ```