未排序数组的线性搜索优化：能否将计算量减半？

嘿，这个问题问得很务实！咱们先明确结论：对于未排序的数组，确实能通过简单的优化把线性搜索的平均计算量减少约一半——虽然最坏情况的开销没法完全避免，但平均场景下的效率提升很明显。

先聊聊基础线性搜索的问题 #

你给出的基础线性搜索伪代码是从数组一头逐个遍历：

i <- 1
while i<=length[a] && a[i]!=v do
    i <- i+1
if i>length[a] then return NIL else return i

这种方法的问题是：如果目标元素存在，平均需要遍历数组的一半元素（n/2次比较）；如果目标不存在，必须遍历完所有n个元素。

针对未排序数组的核心优化：双向线性搜索 #

最直接有效的优化思路是同时从数组的首尾两端向中间扫描——每次循环检查两个元素，要么找到目标，要么向中间收缩指针。这样一来，平均情况下的比较次数会直接减半。

优化后的伪代码

i <- 1
j <- length[a]
result <- NIL
while i <= j do
    # 检查左指针位置的元素
    if a[i] == v then
        result <- i
        break
    # 检查右指针位置的元素
    if a[j] == v then
        result <- j
        break
    # 未找到则向中间收缩
    i <- i + 1
    j <- j - 1
return result

为什么能减少约一半计算量？

咱们从概率角度分析：

• 假设目标元素在数组中任意位置的概率相等，基础线性搜索平均需要n/2次比较才能找到目标；
• 双向搜索中，目标要么被左指针找到（最多k次比较，k是目标位置），要么被右指针找到（最多n - k + 1次比较）。平均下来，比较次数约为n/4，直接比基础方法减少了一半。

当然也要注意局限性：

• 如果目标不存在，双向搜索仍然需要检查所有n个元素，但循环次数是ceil(n/2)，比基础方法的n次循环减少了一半（循环本身的开销也会降低）；
• 最坏情况（比如目标刚好在数组正中间），双向搜索的比较次数和基础方法差不多，但这种情况的概率很低。

额外说明：排序数组 vs 未排序数组 #

你提到排序数组可以用二分查找把复杂度降到O(logn)，这没错，但排序本身需要O(nlogn)的开销——如果只是做一次搜索，排序的成本远高于线性搜索的优化；只有当需要多次搜索时，排序才划算。而咱们讨论的双向搜索是针对未排序数组单次/少量搜索的最优轻量优化方案。

内容的提问来源于stack exchange，提问作者BeginningMath