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)，最快	冲突处理复杂、不支持有序遍历	关键字集合大、仅按值查询

核心操作 / 算法

顺序查找：for i in 0..n-1: if a[i]==key return i。
折半查找（迭代版）：lo=0, hi=n-1，mid = lo+(hi-lo)/2；a[mid]==key 命中，a[mid]<key 则 lo=mid+1，否则 hi=mid-1；lo>hi 时失败。
折半查找（递归版）：递归边界 lo>hi，中间位置判定后向一半区间递归。
分块查找：先在索引表定位块，再在块内顺序查找。
哈希查找（链地址法）：hash(key) = key % size 定位桶，在该桶链表内顺序比较。
平均查找长度 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）和随机化散列函数把概率压到几乎为零。

语言实现

以下四种实现完全等价，每个文件包含两部分演示：

折半查找：同一有序数组，给出迭代与递归两种实现；
哈希查找：用链地址法处理冲突，插入关键字 15, 25, 35, 7, 17, 27, 3, 13（对 10 取模后多处冲突，便于观察冲突处理），再查找命中与未命中元素并打印比较次数。

C

#include <stdio.h>
#include <stdlib.h>

/* ---------- 折半查找（二分） ---------- */

// 迭代版：在有序数组 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++

#include <iostream>
#include <vector>
#include <list>
using namespace std;

/* ---------- 折半查找（二分） ---------- */

// 迭代版
int binarySearchIterative(const vector<int>& 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<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);
}

/* ---------- 哈希查找（链地址法） ---------- */

class HashTable {
private:
    vector<list<int>> 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<int> 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

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<LinkedList<Integer>> 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<Integer> 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

"""折半查找（二分）与哈希查找（链地址法）演示"""

# ---------- 折半查找 ----------

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)   # 未命中

19.查找.md 16 KB Lịch sử Raw