1. 概述
在编程中，搜索问题是极为常见的问题，解决方法也多种多样。其中两种常见方法是线性搜索（Linear Search）和二分搜索（Binary Search）。
本文将分别介绍这两种算法的原理与使用场景，并进行对比分析。
2. 线性搜索
2.1 基本原理
线性搜索是一种逐个遍历元素进行比较的搜索方式。它适用于任何数据结构和数据顺序，不需要任何前提条件。
2.2 数组中的线性搜索
线性搜索可用于在数组中查找某个特定值。我们从头开始逐个比较，一旦找到目标值，就返回其索引；若遍历结束仍未找到，则返回 -1。
示例算法如下：
algorithm LinearSearch(A, n, value):
// INPUT
// A = 要搜索的数组
// n = 数组长度
// value = 要查找的值
// OUTPUT
// 返回值所在索引，若未找到则返回 -1
for i <- 1, 2, ..., n:
if A[i] == value:
return i
return -1
✅ 时间复杂度：O(n)，其中 n 为数组长度。
2.3 用于求解问题的线性搜索
线性搜索也可用于在某个范围内寻找最大可行解的问题。
例如，我们想找出在给定资金下最多能制作多少瓶果汁。假设有一个 canMake(i) 函数，用于判断是否能制作 i 瓶果汁。我们从最小值开始尝试，直到不能再制作为止。
示例算法如下：
algorithm FindMaxAcceptedAnswer(low, high):
// INPUT
// low = 最小可能解
// high = 最大可能解
// OUTPUT
// 返回满足 canMake 的最大值，若无则返回 -1
answer <- -1
for i <- low, low + 1, ..., high:
if canMake(i):
answer <- i
else:
break
return answer
✅ 时间复杂度：O(n)，其中 n 为范围长度。
⚠️ 缺点：效率较低，尤其当范围很大时，会显著拖慢程序运行。
3. 二分搜索
3.1 基本原理
二分搜索的核心思想是将搜索范围一分为二，通过比较中间值决定下一步搜索的方向，从而快速缩小范围。
3.2 数组中的二分搜索
使用二分搜索的前提是数组必须有序。我们定义左右边界 low 和 high，每次取中间值 mid，根据比较结果决定向左还是向右继续搜索。
示例算法如下：
algorithm BinarySearch(A, n, value):
// INPUT
// A = 要搜索的数组
// n = 数组长度
// value = 要查找的值
// OUTPUT
// 返回值所在索引，若未找到则返回 -1
low <- 1
high <- n
answer <- -1
while low <= high:
mid <- (low + high) / 2
if A[mid] == value:
answer <- mid
break
else if A[mid] < value:
low <- mid + 1
else:
high <- mid - 1
return answer
✅ 时间复杂度：O(log n)，远优于线性搜索。
3.3 用于求解问题的二分搜索
二分搜索也可以用于求解某些特定问题，前提是答案范围必须满足单调性：即存在一个临界点，使得该点之前的所有值都满足条件，之后都不满足。
例如，我们仍用 canMake(i) 函数判断是否能制作 i 瓶果汁。我们设定初始范围 [low, high]，每次取中间值 mid：
- 若
canMake(mid)为true，说明最大值可能在右边，更新low - 否则说明当前值过大，更新
high
示例算法如下：
algorithm BinarySearchForProblemAnswer(low, high):
// INPUT
// low = 最小可能解
// high = 最大可能解
// OUTPUT
// 返回满足 canMake 的最大值，若无则返回 -1
answer <- -1
while low <= high:
mid <- (low + high) / 2
if canMake(mid):
answer <- mid
low <- mid + 1
else:
high <- mid - 1
return answer
✅ 时间复杂度：O(log n)，适用于大规模范围的搜索问题。
⚠️ 注意：必须确保 canMake 函数的返回值随输入单调变化，否则不能使用二分搜索。
4. 线性搜索 vs 二分搜索
| 特性 | 线性搜索 | 二分搜索 |
|---|---|---|
| 数组是否需要排序 | ❌ 不需要 | ✅ 必须排序 |
| 是否适用于问题求解 | ✅ 可用 | ✅ 有条件可用 |
| 时间复杂度 | O(n) |
O(log n) |
| 适用范围 | 通用性强 | 需满足单调性 |
✅ 总结：如果问题满足二分搜索的条件，应优先使用二分搜索，因其效率远高于线性搜索。
5. 总结
本文分别介绍了线性搜索与二分搜索的原理、实现方式及其在数组查找和问题求解中的应用。通过对比可以看出：
- 线性搜索通用性强，但效率低；
- 二分搜索效率高，但有使用前提（排序或单调性）。
在实际开发中，遇到大规模数据或需频繁搜索的场景时，应优先考虑二分搜索以提升性能。掌握这两种算法，有助于我们在不同场景下做出合理选择。