从大海捞针到一步到位：两种查找算法的可视化演示

上篇聊了排序，这篇接着聊查找。

「查找」可能是大家平时用得最多、却最没感觉的操作。打开手机通讯录找一个人、在搜索引擎里搜关键词、甚至在超市货架上找某瓶酱油——本质上都是查找。

区别在于方法。你在一堆杂乱的纸条里翻找，和在一本按字母排好序的词典里翻找，效率天差地别。对应到计算机里，就是「顺序查找」和「二分查找」的区别。

废话不多说，先看直观感受，再讲道理。

查找是什么问题

查找问题的定义很简单：给你一组数据和一个目标值，问目标值在不在这组数据里？如果在，在哪个位置？

衡量查找算法的核心指标是「比较次数」——需要检查多少个元素才能得出结论。数据量越大，好算法和差算法之间的效率差距越明显。

比如在 100 万条数据中查找一个值：

• 顺序查找最坏要比较 100 万次
• 二分查找最多只要比较大约 20 次

差距就是这么夸张。下面我们逐个看。

顺序查找——从头到尾逐个找

顺序查找是最朴素的方法：从数组的第一个元素开始，一个一个往后看，碰到目标值就返回位置，全部看完还没找到就说明不存在。

Python 代码如下：

def 顺序查找(数组, 目标值):
    for i in range(len(数组)):            # 从头到尾遍历每个元素
        if 数组[i] == 目标值:              # 如果找到目标值
            return i                       # 返回它的位置（索引）
    return -1                              # 遍历完都没找到，返回 -1

# 测试代码
测试数据 = [10, 20, 30, 42, 50]
目标 = 42
索引 = 顺序查找(测试数据, 目标)
print(f"数据: {测试数据}")
print(f"在其中查找: {目标}")
print(f"查找到的位置索引: {索引}")

简单到不需要解释。但也正因为简单，它的时间复杂度是 O(n)——数据量翻倍，最坏情况下查找时间也翻倍。

在下面的演示中，输入一个目标值，看看顺序查找是怎么一个一个「扫」过去的：

二分查找——折半缩小范围

二分查找的前提是：数据必须是有序的。

思路也很好理解——想象你在猜一个 1 到 100 之间的数字，每次猜完别人告诉你「大了」或「小了」。最聪明的策略是什么？当然是每次猜中间值，一下子排除一半的可能。

Python 代码：

def 二分查找(数组, 目标值):
    左边界 = 0                            # 搜索范围的左端
    右边界 = len(数组) - 1                # 搜索范围的右端
    while 左边界 <= 右边界:                # 只要搜索范围还有元素
        中间位置 = (左边界 + 右边界) // 2  # 取中间位置（整数除法取下取整）
        if 数组[中间位置] == 目标值:        # 中间值刚好是目标值
            return 中间位置                 # 找到了，返回位置
        elif 数组[中间位置] < 目标值:      # 中间值比目标小，说明目标在右半边
            左边界 = 中间位置 + 1           # 缩小范围：只看右半边
        else:                              # 中间值比目标大，目标在左半边
            右边界 = 中间位置 - 1           # 缩小范围：只看左半边
    return -1                              # 范围为空仍未找到，目标不存在

# 测试代码
测试数据 = [10, 20, 30, 42, 50]
目标 = 42
索引 = 二分查找(测试数据, 目标)
print(f"有序数据: {测试数据}")
print(f"在其中查找: {目标}")
print(f"查找到的位置索引: {索引}")

三个变量：left（左边界）、right（右边界）、mid（中间位置）。每次比较完中间值，要么找到了，要么把搜索范围砍掉一半。

在下面的演示中，注意看灰色区域（已被排除的范围）是怎么一步步扩大的，紫色格子是当前的中间值：

竞速对比——同屏见真章

光分别看两种查找可能还没什么感觉。我们让它们来场「赛跑」——在同一组数据中查找同一个目标值，两种算法同步执行，看谁先找到。

数据量越大，差距越明显。建议试试把数据设到 20 个以上再看效果。

什么时候用哪种

简单总结：

• 数据量小（几十个以内），顺序查找足矣，别过度设计
• 数据量大且有序，二分查找是首选
• 如果数据无序但需要频繁查找，比较好的做法是先排序再二分
• 需要 O(1) 级别的查找速度？那就该用「哈希表」了，Python 里就是 dict 和 set

进阶扩展——哈希查找与树结构

顺便提一下两种更高级的查找方式，这里只做简介，以后有机会单独写。

哈希查找：通过一个「哈希函数」直接计算出目标值的存储位置，平均时间复杂度是 O(1)，堪称查找界的「传送门」。Python 的 dict 底层就是哈希表。代价是需要额外的存储空间，且不支持范围查询。

二叉搜索树：把数据组织成树形结构，左子节点小于父节点，右子节点大于父节点。查找时从根节点出发，每次二选一往下走。平衡状态下时间复杂度也是 O(log n)，但它比二分查找更擅长动态数据的插入和删除。

总结

查找和排序是算法世界的两块基石。掌握了今天讲的顺序查找和二分查找，你就理解了「暴力」和「优化」之间的核心差距——面对同一个问题，选对方法能把效率提升几个数量级。

建议大家回到竞速对比那个演示区多玩几遍，把数据量调大一些，亲眼看看 O(n) 和 O(log n) 的差距有多大。有些东西，看一遍比背十遍有效。

如果你还没看过上一篇排序算法的文章，也推荐回去看看，同样有交互演示和四种排序竞速对比。