在我们的日常学习和生活中，经常会遇到“找东西”的场景。比如在字典里查一个单词，在电话簿里找一个电话号码，或者在列表里找某个商品的价格。这些“找东西”的过程，在计算机里就对应着查找算法。查找算法有很多种，今天我们就从最简单的线性查找开始，逐步了解更高效的二分查找，看看它到底快在哪里。

一、什么是线性查找？¶

线性查找（也叫顺序查找）是最基础的查找方法，它的原理非常简单：从头到尾逐个检查数据，直到找到目标元素。

举个例子：假设我们有一个数组 [2, 5, 8, 12, 16]，要找数字 8。

• 第一步：检查第一个元素 2，不是目标；
• 第二步：检查第二个元素 5，不是目标；
• 第三步：检查第三个元素 8，找到了！

如果目标元素不存在，线性查找会遍历整个数组后才结束。

线性查找的特点：¶

• 时间复杂度：
• 最好情况：目标元素就在第一个位置，只需 1 次查找（记为 O(1)）；
• 最坏情况：目标元素在最后一个位置，或不存在，需要遍历整个数组（记为 O(n)，其中 n 是数据量）；
• 平均情况：还是 O(n)，因为平均需要检查一半的数据。

比如，当数据量是 10000 个时，线性查找最坏可能需要 10000 次查找，这在大数据量下效率非常低。

二、二分查找：从“逐个检查”到“对半排除”¶

线性查找的缺点是效率低，尤其是数据量大的时候。有没有更快的方法呢？当然有，这就是二分查找（Binary Search）。

二分查找的前提：¶

二分查找只能在有序数组中使用（比如从小到大或从大到小排列的数组）。如果数组是无序的，二分查找就不适用了。

二分查找的原理：¶

它的核心思想是“每次排除一半的数据”。具体来说：
1. 先找到数组的中间位置，比较中间元素和目标元素；
2. 如果中间元素等于目标，直接找到；
3. 如果中间元素比目标大，说明目标在中间元素的左边，接下来只需要在左半部分继续查找；
4. 如果中间元素比目标小，说明目标在中间元素的右边，接下来只需要在右半部分继续查找；
5. 重复上述步骤，直到找到目标或确定不存在。

用例子理解二分查找：¶

还是刚才的有序数组 [2, 5, 8, 12, 16]，现在找数字 8。

• 第一次查找：数组长度是 5，中间位置是第 2 个元素（索引 2，数值 8）。正好等于目标，直接找到！

再举一个复杂点的例子：找 12。

• 第一次查找：中间位置是第 2 个元素（数值 8）。因为 8 < 12，所以目标在右半部分，剩下的数组是 [12, 16]；
• 第二次查找：新数组长度是 2，中间位置是第 1 个元素（数值 12）。等于目标，找到！

二分查找的时间复杂度：¶

每次查找都会排除一半的数据，所以查找次数与数据量的“对数”相关。时间复杂度记为 O(log n)（log 是对数，这里默认以 2 为底）。

比如：
- 数据量 n=1000 时，log₂(1000) ≈ 10（即最多 10 次查找）；
- 数据量 n=10000 时，log₂(10000) ≈ 14（最多 14 次查找）；
- 数据量 n=1000000 时，log₂(1000000) ≈ 20（最多 20 次查找）。

三、二分查找比线性查找快多少？¶

我们用具体数据对比一下：

关键结论：当数据量 n 越大时，二分查找的速度优势越明显。比如 n=100 万时，二分查找只需 20 次，而线性查找要 100 万次，差距高达 5 万倍！

四、什么时候用二分查找？什么时候用线性查找？¶

二分查找适用场景：¶

• 数据是有序的（如已排序的列表、数组）；
• 数据量较大（此时效率优势更明显）；
• 需要频繁查找（二分查找的“准备时间”是排序，但如果是固定有序数组，后续查找很高效）。

线性查找适用场景：¶

• 数据是无序的（无法使用二分查找）；
• 数据量非常小（比如只有几个元素，线性查找反而更简单，无需额外准备）；
• 数据是动态变化的（频繁插入/删除会破坏有序性，线性查找更灵活）。

五、总结：二分查找的核心价值¶

二分查找是数据结构中经典的“高效查找技巧”，它通过“对半排除”的策略，将查找次数从 O(n) 降到 O(log n)，在大数据量下效率远超线性查找。但要记住：有序数组是二分查找的前提，如果数据无序，就只能用线性查找。

对于初学者来说，理解二分查找的“排除一半”逻辑，掌握它的时间复杂度分析，以及和线性查找的对比，就能在实际问题中根据数据特点选择合适的查找方法。随着数据量的增长，二分查找的优势会越来越突出，这也是它成为算法面试和实际开发中高频考点的原因。