第25章查找算法

课程目录第25章查找算法

查找算法：顺序查找、二分查找、哈希查找

查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年嵌入式开发，几乎每个项目都离不开查找。小到按键扫描，大到文件系统索引，查找算法的选择直接决定了系统的响应速度。今天咱们就把三种最经典的查找算法掰开揉碎了讲清楚。

1. 顺序查找 —— 最笨但最可靠的方法

顺序查找的思路简单到令人发指：从第一个元素开始，挨个比，直到找到目标值。你想想看，这就像在一堆钥匙里找你家那把，一把一把试。

基本原理：遍历整个数组，逐个比较元素与目标值。时间复杂度 O(n)，空间复杂度 O(1)。

适用场景：数据量小（比如几十个元素），或者数据无序。我在调试一个老旧传感器模块时，数据量就十几个字节，用顺序查找完全够用，写起来还快。

  核心要点：顺序查找不要求数据有序，实现简单，但效率随数据量线性下降。

// 顺序查找：返回目标值的索引，未找到返回 -1
int sequential_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;   // 找到了，返回位置
        }
    }
    return -1;          // 没找到
}

这段代码我闭着眼都能写。但要注意一点：如果数组很大，比如几千个元素，顺序查找就会很慢。我曾经在一个项目里用顺序查找查一个 2000 个元素的表，结果每次按键响应都卡顿。后来换成二分查找，问题立刻解决。

小技巧：如果数据经常变动（增删改），顺序查找反而有优势——它不需要维护有序性。

2. 二分查找 —— 快就一个字

二分查找的前提是数据必须有序。它的思路是：每次取中间元素比较，如果目标比中间值小，就去左半边找；比中间值大，就去右半边找。每次都能排除一半的数据。

时间复杂度 O(log n)，空间复杂度 O(1)（迭代版本）。

为什么这么快？ 你想想看，1000 个有序数据，顺序查找最坏要比较 1000 次，二分查找最多比较 10 次（2^10 = 1024）。差距就是这么大。

注意：二分查找的前提是数组必须有序。如果数据无序，先排序再查找，总成本可能比顺序查找还高。我见过有人拿无序数组直接跑二分查找，结果查不到数据还一脸懵——嗯，排序这步不能省。

// 二分查找（迭代版本）：返回目标值的索引，未找到返回 -1
int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

这里有个细节：mid = left + (right - left) / 2 而不是 (left + right) / 2。为什么？因为 left + right 可能溢出。我在一个 32 位单片机上吃过这个亏，数组索引用 int，当 left 和 right 都接近 2^31 时，一加就溢出了。后来改成这种写法，再也没出过问题。

避坑指南：我曾经在嵌入式项目中用递归实现二分查找，结果栈空间不够，直接死机。后来全部改成迭代版本，稳得很。嵌入式环境里，递归要慎用。

3. 哈希查找 —— 用空间换时间

哈希查找的思路是：通过一个哈希函数，把关键字直接映射到存储位置。理想情况下，时间复杂度 O(1)。

说白了，就是给每个数据算一个“身份证号”，然后根据这个号直接去对应位置取数据。不需要比较，一步到位。

基本原理：

设计哈希函数（比如取模运算）
将关键字映射到数组下标
处理冲突（不同关键字映射到同一位置）

常见的冲突处理方法有：链地址法（每个位置挂一个链表）、开放地址法（找下一个空位）。

  核心要点：哈希查找的查找速度极快，但需要额外的存储空间，且哈希函数的设计直接影响性能。

// 简单的哈希查找（链地址法示例）
#include <stdlib.h>

#define TABLE_SIZE 100

typedef struct Node {
    int key;
    int value;
    struct Node *next;
} Node;

Node* hash_table[TABLE_SIZE];

// 哈希函数：取模
int hash(int key) {
    return key % TABLE_SIZE;
}

// 插入
void insert(int key, int value) {
    int index = hash(key);
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

// 查找
int search(int key) {
    int index = hash(key);
    Node *cur = hash_table[index];
    while (cur != NULL) {
        if (cur->key == key) {
            return cur->value;
        }
        cur = cur->next;
    }
    return -1;  // 未找到
}

哈希查找在嵌入式里用得也很多，比如缓存系统、快速查表。但要注意：哈希表会占用额外内存，而且哈希函数如果设计不好，冲突太多，性能会退化到 O(n)。

注意：在内存受限的嵌入式系统中，哈希表可能不是最佳选择。我曾经在一个只有 4KB RAM 的 MCU 上尝试用哈希表，结果内存直接爆了。后来改用二分查找，虽然慢一点，但内存够用。

三种算法对比

算法	时间复杂度	空间复杂度	数据要求	适用场景
顺序查找	O(n)	O(1)	无	数据量小，或数据无序
二分查找	O(log n)	O(1)	有序	数据量大且有序，内存有限
哈希查找	O(1) 平均	O(n)	需设计哈希函数	查找频繁，内存充足

知识体系图

下面这张图帮你理清三种查找算法的核心逻辑和选择依据。

如何选择？

我个人习惯这样选：

数据量小于 50：顺序查找，代码简单，维护方便。
数据量大且有序：二分查找，内存占用小，速度快。
查找非常频繁，内存够用：哈希查找，一步到位。

记住一点：没有银弹。我在一个项目里同时用了二分查找和哈希表——启动时用二分查找加载配置，运行时用哈希表快速查询。各取所长，才是工程之道。

我的经验：在嵌入式开发中，优先考虑二分查找。因为它不额外占用内存，而且 O(log n) 的速度对大多数场景已经足够。哈希表虽然快，但内存开销和哈希函数的设计成本，有时候得不偿失。

好了，三种查找算法就讲到这里。代码都给你了，原理也讲透了，剩下的就是多写多练。遇到实际问题时，想想今天说的这些，选一个最合适的。

📚 课程目录

查找算法：顺序查找、二分查找、哈希查找

1. 顺序查找 —— 最笨但最可靠的方法

2. 二分查找 —— 快就一个字

3. 哈希查找 —— 用空间换时间

三种算法对比

知识体系图

如何选择？