第19章查找算法

课程目录第19章查找算法

查找算法：线性查找、二分查找、哈希查找

查找，说白了就是在一堆数据里找到你想要的那个。听起来简单吧？但实际写代码时，不同场景下的查找效率能差出几个数量级。我早年做嵌入式项目时，就因为在循环里用了低效的查找方式，导致整个系统响应延迟，被客户追着改了好几个版本。

今天咱们就把三种最基础的查找算法掰开揉碎讲清楚。线性查找、二分查找、哈希查找，这三种方法各有各的脾气，用对了地方就是神器，用错了就是灾难。

核心要点：查找算法的本质是「空间换时间」或「时间换空间」的权衡。没有绝对的好坏，只有合不合适的场景。

一、线性查找——最朴素的暴力美学

线性查找，也叫顺序查找。它的逻辑简单到令人发指：从第一个元素开始，挨个比较，直到找到目标值或者遍历完整个数组。

你可能会想：「这也算算法？」嗯，算。而且在实际项目中，它往往是最先被想到的方案。我记得有一次调试一个传感器数据采集程序，数据量只有几十个字节，我直接用线性查找，代码写起来快，调试也方便。

// 线性查找 - 最基础的实现
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 找到了，返回索引
        }
    }
    return -1;  // 没找到
}

小技巧：如果你确定数据中一定存在目标值，可以省略最后的 -1 判断。但我不建议这么做——万一数据出问题，返回一个错误索引比返回 -1 更难排查。

线性查找的时间复杂度是 O(n)。说白了，数据量翻倍，查找时间也翻倍。在数据量小于 100 的场景下，这完全够用。但如果你在 10 万条数据里用线性查找，那体验就有点糟糕了。

注意：我曾经在一个循环中嵌套了线性查找，外层循环 1000 次，内层查找 5000 条数据。结果程序跑一次要 5 秒。后来改成哈希查找，瞬间降到 10 毫秒。所以，线性查找虽好，可不要贪杯哦。

二、二分查找——有序世界的快速通道

二分查找的前提很苛刻：数据必须有序。但一旦满足这个条件，它的效率就非常可观了。每次比较都能排除一半的数据，时间复杂度只有 O(log n)。

你想想看，在 100 万条有序数据里找某个值，线性查找最多要比较 100 万次，而二分查找最多只需要 20 次。这就是差距。

// 二分查找 - 迭代实现
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 位嵌入式系统上就踩过这个坑，数组索引超过 2^31 时直接崩了。

二分查找也可以用递归实现，代码更简洁，但递归调用有栈开销。在嵌入式环境里，我一般用迭代版本，省栈空间，也更容易控制。

// 二分查找 - 递归实现（了解即可）
int binary_search_recursive(int arr[], int left, int right, int target) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) 
        return binary_search_recursive(arr, mid + 1, right, target);
    else 
        return binary_search_recursive(arr, left, mid - 1, target);
}

避坑指南：二分查找的边界条件非常容易写错。我建议你记住一个原则：while (left <= right) 配合 left = mid + 1 和 right = mid - 1。这个组合最不容易出错。如果你用 left < right，那就要小心处理边界了。

三、哈希查找——用空间换时间的极致

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

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

// 简单的哈希表实现 - 链地址法解决冲突
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 100

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

typedef struct {
    Node** buckets;
    int size;
} HashTable;

// 哈希函数 - 取模法
int hash_func(int key, int size) {
    return abs(key) % size;
}

// 创建哈希表
HashTable* create_table(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = (Node**)calloc(size, sizeof(Node*));
    return table;
}

// 插入键值对
void insert(HashTable* table, int key, int value) {
    int index = hash_func(key, table->size);
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
}

// 查找
int search(HashTable* table, int key) {
    int index = hash_func(key, table->size);
    Node* current = table->buckets[index];
    
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return -1;  // 没找到
}

个人经验：哈希函数的选择很关键。取模法虽然简单，但如果 key 分布不均匀，会导致大量冲突。我在项目中常用的是「乘法取整法」或者对字符串用「BKDR 哈希」。记住一点：好的哈希函数能让数据均匀分布，减少链表长度。

哈希查找的缺点也很明显：需要额外的内存空间来存储哈希表。在嵌入式系统中，如果内存紧张，哈希表可能不是最佳选择。另外，哈希表不支持范围查找——你想找「大于 100 的所有元素」？哈希表做不到。

三种算法对比

算法	时间复杂度	空间复杂度	数据要求	适用场景
线性查找	O(n)	O(1)	无要求	小数据量、无序数据
二分查找	O(log n)	O(1)	必须有序	有序数据、静态数据集
哈希查找	O(1) 平均	O(n)	需要哈希函数	快速查找、键值对场景

我的建议：在实际项目中，不要一开始就追求「最高效」的算法。先评估数据量和场景。数据量小于 1000 且查找不频繁？线性查找就够了。数据有序且查找频繁？二分查找是首选。需要极速查找且内存充足？哈希表是你的好帮手。

这三种查找算法是基础中的基础。你可能会觉得它们太简单，但说实话，我在工作中见过太多因为选错查找算法而导致的性能问题。把这三个吃透了，你就能应对 90% 以上的查找场景。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

查找算法：线性查找、二分查找、哈希查找

一、线性查找——最朴素的暴力美学

二、二分查找——有序世界的快速通道

三、哈希查找——用空间换时间的极致

三种算法对比