36、查找算法：线性查找、二分查找（递归与非递归）、哈希查找的概念

查找，说白了就是在一堆数据里找到你想要的那个。

我做了这么多年C语言开发，可以说查找算法是日常编码中最基础也最常用的操作之一。不管是嵌入式设备里查传感器数据，还是后台服务里查用户信息，都离不开它。

今天咱们就把三种最经典的查找算法掰开揉碎讲清楚。我个人习惯把它们分成两类：无脑遍历型和聪明跳转型。

线性查找——最笨但最可靠

线性查找的思路简单到令人发指：从头到尾，一个一个比。找到了就返回位置，找不到就拉倒。

我在项目中遇到过这么个场景：一个嵌入式设备里存了200个温度传感器的ID，每次要查某个ID是否存在。数据量不大，而且ID是无序的。我当时想都没想就用了线性查找——为什么？因为简单、不易出错、代码量少。你想想看，200个数据，线性查找最多查200次，对CPU来说就是一瞬间的事。

// 线性查找 —— 最朴素的实现
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到100之间的一个数，你每次猜完我会告诉你「大了」还是「小了」。你肯定不会从1开始一个一个猜吧？你会先猜50，然后根据反馈缩小范围。

二分查找就是这个道理。

递归实现

递归版本写起来很优雅，但要注意栈溢出的问题。我记得有一次在面试里，有个小伙子递归写得很漂亮，但我问他「如果数组有10万个元素会怎样」，他愣了一下——嗯，递归深度太大，栈会爆。

// 二分查找 —— 递归版本
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;
    } else if (arr[mid] > target) {
        return binary_search_recursive(arr, left, mid - 1, target);
    } else {
        return binary_search_recursive(arr, mid + 1, right, target);
    }
}

非递归实现

非递归版本是我个人更推荐的。它没有函数调用开销，也不会栈溢出，性能更好。

// 二分查找 —— 非递归版本
int binary_search_iterative(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

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

哈希查找就更有意思了。它不比较，而是直接算。通过一个哈希函数，把关键字映射到一个位置，然后直接去那个位置取数据。

你想想看，这就像图书馆里每本书都有一个索书号，你根据索书号直接去对应的书架找就行了，不用一本一本翻。

在C语言里，没有现成的哈希表，得自己实现。不过标准库里的 uthash 是个好东西，我项目里经常用。

// 一个简单的哈希查找示例（使用链地址法解决冲突）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 100

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

Entry* hash_table[TABLE_SIZE];

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

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

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

三种算法对比

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

知识体系总览

下面这张图帮你理清三种查找算法的核心逻辑和适用场景：

总结一下

三种查找算法各有千秋，没有银弹。我个人的选择原则很简单：

• 数据量小（<1000）：线性查找，代码简单，不易出错。
• 数据量大且有序：二分查找，非递归版本优先。
• 需要频繁查找，数据动态变化：哈希查找，但要注意哈希函数的设计。

嗯，这三种算法是面试里的常客，也是实际开发中的基本功。把它们吃透了，很多场景下你都能快速找到最合适的方案。

---

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