algorithm - 哨兵线性搜索是否优于普通线性搜索？

Question

在传统的线性搜索中，有n个比较用于与所需数量进行比较n+1 为循环条件，总计进行 2n+1 次比较。但是，如果我们按照下面的程序进行，我们最多可以在 n+2 次比较中得到我们的答案。

def sentinelSearch(ar,n,l):
# ar : array
# n : item to be searched
# l : size of array
last = ar[l-1] # saving last element in other variable
ar[l-1] = n # assigning last element as required
i = 0
while ar[i]!=n:
    i+=1
ar[l-1] = last
if (i<l-1) or n==ar[l-1]:
    print('Item found at',i)
else:
    print('Item not Found')

尽管如此，两种算法的最坏情况时间复杂度都是 O(n)。只是减少了比较的次数，这是否会使这种“前哨线性搜索”算法成为搜索未排序数组的更好算法？

Answer 1

您必须对其进行基准测试。但是有多种因素会影响结果，例如:

• 分支预测。检查某些条件比其他条件便宜。
• 编译器优化。很多时候，数组循环展开，而您实际上对循环条件进行的比较少于 n 次。

此外，正如评论中提到的那样，您的算法必须改变数组(通常不好)并且您必须为哨兵保留特殊值(并非总是可能)。因此，优化的真正好处实际上可以忽略不计。