查找基础：从顺序到折半，再到分块

查找，说白了就是在一堆数据里找到你想要的那个。这事儿听起来简单，但实际做起来门道不少。我做了这么多年嵌入式开发，几乎每个项目都离不开查找操作——从传感器数据检索到配置表匹配，查找算法的好坏直接决定了系统的响应速度。

今天咱们就把查找的三种基本方法捋一遍：顺序查找、折半查找、分块查找。这三种方法各有各的脾气，用对了地方就是利器，用错了就是灾难。

什么是查找？

查找，就是根据给定的关键字，在一组数据中找到对应的记录。关键字可以是学号、姓名、或者某个传感器的ID。

我习惯把查找分为两类：静态查找和动态查找。静态查找就是数据不变，只查不改；动态查找则允许插入和删除。今天讲的三种方法都属于静态查找范畴。

顺序查找：最笨但最可靠

顺序查找，就是从头到尾一个一个比。你想想看，这方法虽然笨，但有个好处——不挑数据。不管数据是有序还是无序，都能用。

我在项目中遇到过这样的情况：一个嵌入式设备启动时，需要从配置表里查找某个外设的初始化参数。配置表只有几十条记录，而且经常变动，用顺序查找反而最省事——代码简单，不容易出bug。

// 顺序查找 - 最朴素的实现
int seq_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // 找到了，返回下标
        }
    }
    return -1;  // 没找到
}

这段代码没什么花哨的，就是循环加比较。平均查找长度是 (n+1)/2，也就是说数据量翻倍，查找时间也翻倍。

// 带哨兵的顺序查找
int seq_search_sentinel(int arr[], int n, int key) {
    int i = 0;
    arr[n] = key;  // 放置哨兵
    while (arr[i] != key) {
        i++;
    }
    return (i < n) ? i : -1;  // 如果i==n说明没找到
}

折半查找：快，但有条件

折半查找，也叫二分查找。这名字起得好——每次把查找范围折掉一半。效率高得吓人，但前提是数据必须有序。

我记得有一次做车载导航系统，需要从几十万个POI（兴趣点）里快速查找某个地点。数据是按拼音排序的，用折半查找，每次查找只需要比较十几次，比顺序查找快了不知道多少倍。

// 折半查找 - 递归实现
int binary_search_recursive(int arr[], int left, int right, int key) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;  // 防止溢出
    
    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        return binary_search_recursive(arr, left, mid - 1, key);
    } else {
        return binary_search_recursive(arr, mid + 1, right, key);
    }
}

// 折半查找 - 迭代实现（我更喜欢这个）
int binary_search_iterative(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

折半查找的时间复杂度是 O(log n)。什么意思呢？1000个数据，最多比较10次；100万个数据，最多比较20次。这效率，你品品。

分块查找：折中的智慧

分块查找，也叫索引顺序查找。它把数据分成若干块，块内可以无序，但块与块之间必须有序。说白了，就是第一块的所有数据都比第二块小，第二块比第三块小，以此类推。

我为什么说它折中？因为它结合了顺序查找和折半查找的优点。查找时先在索引表里用折半查找找到目标所在的块，然后在块内用顺序查找。既不用全排好序，又比纯顺序查找快。

// 分块查找的简单实现
typedef struct {
    int max_key;  // 块内最大关键字
    int start;    // 块起始位置
    int length;   // 块长度
} IndexBlock;

int block_search(int arr[], IndexBlock blocks[], int block_num, int key) {
    // 1. 在索引表中查找目标块
    int block_idx = -1;
    for (int i = 0; i < block_num; i++) {
        if (key <= blocks[i].max_key) {
            block_idx = i;
            break;
        }
    }
    if (block_idx == -1) return -1;
    
    // 2. 在目标块内顺序查找
    int start = blocks[block_idx].start;
    int end = start + blocks[block_idx].length;
    for (int i = start; i < end; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

三种方法怎么选？

我个人的经验是这么选的：

• 数据量小（几十个以内）：用顺序查找。代码简单，维护方便，性能差别不大。
• 数据量大且有序：用折半查找。这是首选，没有之一。
• 数据量大但无序，或者需要频繁插入删除：考虑分块查找。块内无序，插入删除方便；块间有序，查找效率有保障。

算法	时间复杂度	数据要求	适用场景
顺序查找	O(n)	无要求	小数据量，或无序数据
折半查找	O(log n)	必须有序	大数据量，静态数据
分块查找	O(log m + k)	块间有序	动态数据，索引查找

最后说一句：别小看查找算法。我见过太多项目因为选错了查找方式，导致系统响应慢得让人抓狂。选对算法，你的代码就跑得快；选错了，再牛的硬件也救不了你。