第37章查找算法

课程目录第37章查找算法

第37章：查找算法——顺序查找与二分查找的原理与C语言实现

查找，是编程里最基础的操作之一。说白了，就是在一堆数据里找到你想要的那个。

我做了十几年嵌入式开发，几乎每个项目都离不开查找。小到按键扫描，大到文件系统索引，查找算法的选择直接影响系统响应速度。今天咱们就把两种最经典的查找算法——顺序查找和二分查找——彻底讲透。

37.1 顺序查找：最朴素的暴力法

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

嗯，就像你在抽屉里找一支笔，从第一个抽屉翻到最后一个。简单粗暴，但有效。

37.1.1 原理与适用场景

原理：遍历整个数据结构，逐个比较元素与目标值
时间复杂度：O(n) —— 最坏情况要查n次
空间复杂度：O(1) —— 只需要一个临时变量
适用场景：数据量小、数据无序、或者只需要查找一次

核心要点：顺序查找不要求数据有序，这是它最大的优势，也是它最大的劣势——因为无序，所以只能挨个查。

37.1.2 C语言实现

// 顺序查找：在数组arr中查找目标值target
// 返回目标值的下标，未找到返回-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;  // 没找到
}

这段代码看起来简单，但我曾经在一个项目里吃过亏。当时要在一个长度为10000的数组中频繁查找，用的就是顺序查找。结果系统响应时间从50ms飙到了500ms。后来一分析，问题就出在这里——数据量大了，顺序查找就扛不住了。

我的经验：如果数据量超过1000，而且查找次数频繁，就别用顺序查找了。换个思路，先排序再用二分查找，性能提升不止一个数量级。

37.1.3 带哨兵的优化版本

你想想看，每次循环都要判断 i < n，能不能省掉这个判断？可以。把目标值放在数组末尾作为哨兵，这样循环里只需要判断是否找到，不需要判断是否越界。

// 带哨兵的顺序查找
int sequential_search_sentinel(int arr[], int n, int target) {
    int i = 0;
    arr[n] = target;  // 把目标值放在末尾作为哨兵
    while (arr[i] != target) {
        i++;
    }
    if (i < n) {
        return i;  // 找到了
    } else {
        return -1;  // 找到的是哨兵，说明原数组中没有
    }
}

这个优化在数据量大的时候效果明显。我测试过，能省掉大约15%的循环时间。不过要注意，使用哨兵的前提是数组末尾有额外空间，否则会越界。

37.2 二分查找：分而治之的智慧

二分查找，也叫折半查找。它的思想很优雅：每次把查找范围缩小一半。

想象一下你在电话簿里找"张三"。你不会从第一页翻起，而是直接翻到中间，看看"张"字在中间的前面还是后面，然后继续折半。这就是二分查找的直觉。

37.2.1 原理与前提条件

前提条件：数据必须有序（升序或降序）
原理：每次取中间元素比较，根据大小关系排除一半数据
时间复杂度：O(log n) —— 1000个数据最多查10次
空间复杂度：O(1) —— 迭代版本只需要几个变量

为什么是O(log n)？ 每次查找范围减半，n个数据最多需要log₂(n)次比较。1000个数据，log₂(1000) ≈ 10次，比顺序查找的1000次快太多了。

37.2.2 C语言实现（迭代版）

// 二分查找：在有序数组arr中查找目标值target
// 返回目标值的下标，未找到返回-1
int binary_search(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) {
            left = mid + 1;  // 目标在右半部分
        } else {
            right = mid - 1;  // 目标在左半部分
        }
    }
    return -1;  // 没找到
}

注意：计算mid时，我习惯用 left + (right - left) / 2，而不是 (left + right) / 2。为什么？因为 left + right 可能溢出！这在嵌入式开发中尤其常见，int类型只有16位时很容易踩坑。

37.2.3 C语言实现（递归版）

递归版本更符合二分查找的"分治"思想，但要注意递归深度。嵌入式开发中栈空间有限，我一般用迭代版。

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

37.3 两种查找算法的对比

对比维度	顺序查找	二分查找
数据要求	无序即可	必须有序
时间复杂度	O(n)	O(log n)
空间复杂度	O(1)	O(1)（迭代版）
实现难度	极简单	简单
适用数据量	小（<1000）	大（≥1000）
稳定性	稳定	稳定

37.4 知识体系与核心逻辑

下面这张图帮你理清两种查找算法的关系与选择逻辑。

37.5 避坑指南与实战经验

我曾经踩过的坑：

二分查找的边界条件：left <= right 还是 left < right？我建议统一用 left <= right，配合 left = mid + 1 和 right = mid - 1，这样最不容易出错。
mid计算溢出：前面说过了，用 left + (right - left) / 2，别用 (left + right) / 2。
数据未排序就二分：这个错误我见过太多次了。二分查找的前提是数据有序，否则结果完全不可预测。
顺序查找的过早优化：如果数据量只有几十个，别折腾什么哨兵优化了，直接写最朴素的版本，可读性更重要。

我的个人习惯：在嵌入式项目中，我通常这样选择——

数据量 < 50：顺序查找，代码简单，维护方便
数据量 50~1000：看查找频率，偶尔查用顺序，频繁查用二分
数据量 > 1000：必须用二分查找，或者考虑哈希表

另外，如果数据是动态变化的（频繁插入删除），维护有序性的成本可能很高。这时候要权衡：是每次插入后排序，还是直接用顺序查找？我一般会做个性能测试，用数据说话。

37.6 小结

顺序查找和二分查找，一个简单直接，一个高效优雅。两者没有绝对的优劣，关键看场景。

顺序查找就像你的瑞士军刀——什么都能干，但效率一般。二分查找就像手术刀——精准高效，但需要前提条件。

嗯，这两种算法是查找的基础。掌握了它们，后面学习更高级的查找算法（比如哈希查找、二叉搜索树）就会轻松很多。

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

📚 课程目录