查找算法：顺序查找、二分查找、插值查找、斐波那契查找

查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年嵌入式开发，几乎每个项目都离不开查找。从传感器数据表到配置参数，从通信协议到内存管理，查找算法无处不在。

今天咱们就把四种最经典的查找算法掰开揉碎了讲。顺序查找、二分查找、插值查找、斐波那契查找，它们各有各的脾气，也各有各的用武之地。

1. 顺序查找——最朴实的办法

顺序查找，就是从头到尾挨个比。你想想看，如果给你一摞没排序的试卷让你找张三的，你只能一张一张翻，对吧？这就是顺序查找。

它的代码简单到不能再简单：

int sequential_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // 找到了，返回下标
        }
    }
    return -1;  // 没找到
}

时间复杂度：最好O(1)，最坏O(n)，平均O(n)。空间复杂度O(1)。

2. 二分查找——有序世界的利器

二分查找的前提是数据必须有序。它的思路很简单：每次取中间值，比目标大就往左找，比目标小就往右找。每次砍掉一半数据。

我记得刚入行时，有个同事在10000个有序数据里用顺序查找找配置项，每次要等好几秒。我帮他改成二分查找后，瞬间就出结果了。他当时那个表情，我到现在还记得。

int binary_search(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) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

时间复杂度O(log n)。1000个数据最多查10次，100万个数据最多查20次。这就是二分查找的魅力。

3. 插值查找——更聪明的二分

插值查找是二分查找的升级版。二分查找死板地取中间，插值查找会根据目标值大概在什么位置来猜。

打个比方：你在字典里查「张」字，你会从中间翻吗？不会，你会从后面翻。插值查找就是这个思路。

int interpolation_search(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right && key >= arr[left] && key <= arr[right]) {
        // 插值公式：按比例估算位置
        int pos = left + (key - arr[left]) * (right - left) / (arr[right] - arr[left]);
        if (arr[pos] == key) {
            return pos;
        } else if (arr[pos] < key) {
            left = pos + 1;
        } else {
            right = pos - 1;
        }
    }
    return -1;
}

我曾经在一个温度传感器数据表里用过插值查找。温度值在-40°C到85°C之间均匀分布，效果非常好，平均查找次数比二分少了将近一半。

4. 斐波那契查找——没有除法的二分

斐波那契查找，说白了就是用斐波那契数列来分割数组，而不是用除法。为什么不用除法？因为在一些老式的嵌入式芯片上，除法指令很慢，甚至没有硬件除法器。

它的核心思想：用斐波那契数F(k)作为分割点，每次把数组分成F(k-1)和F(k-2)两部分。

int fibonacci_search(int arr[], int n, int key) {
    // 生成斐波那契数列，找到第一个大于等于n的F(k)
    int fib1 = 0, fib2 = 1, fib3 = fib1 + fib2;
    while (fib3 < n) {
        fib1 = fib2;
        fib2 = fib3;
        fib3 = fib1 + fib2;
    }
    
    int offset = -1;  // 已排除部分的偏移量
    while (fib3 > 1) {
        int i = (offset + fib1) < (n - 1) ? (offset + fib1) : (n - 1);
        if (arr[i] < key) {
            fib3 = fib2;
            fib2 = fib1;
            fib1 = fib3 - fib2;
            offset = i;
        } else if (arr[i] > key) {
            fib3 = fib1;
            fib2 = fib2 - fib1;
            fib1 = fib3 - fib2;
        } else {
            return i;
        }
    }
    // 检查最后一个元素
    if (fib2 == 1 && arr[offset + 1] == key) {
        return offset + 1;
    }
    return -1;
}

四种算法对比

嗯，四种查找算法就讲到这里。每种算法都有自己的性格，也都有自己的舞台。你写代码的时候，多想想你的数据长什么样，你的硬件是什么水平，自然就知道该选哪个了。