哨兵线性搜索比正常线性搜索更好吗？

在传统的线性搜索中，与比较所需的数字和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）。只是减少了一些比较，这是否使这个'哨兵线性搜索'更好的算法搜索未经排序的数组或不？

来源

2017-09-12 nirav bharadiya

是的，但它并不总是可能有一个标记，所以它不是一个普遍适用的算法。 – harold

你能告诉我这种情况吗？ –

无聊的实际原因。在多线程上下文中修改共享数组并不安全。或者由于某种原因数组可能实际上是只读的。 – harold

您必须对其进行基准测试。但也有多种因素，这些因素可影响像的结果：

分支预测。检查一些条件比其他条件便宜。
编译器优化。很多时候，数组上的循环被展开，并且实际上对于循环条件做了比n少的比较。

另外，正如人们在评论中提到的，你的算法必须改变数组（通常不是很好），你必须保留特殊值（不总是可能）。因此，优化的真正好处是微不足道的。

来源

2017-09-12 18:19:11 usamec

ohkay！我明白了。同意！ –

哨兵线性搜索比正常线性搜索更好吗？

回答

相关问题