關於二進制搜索中最糟糕的情況

Question

二進制搜索最糟糕的情況是1 + lg n，但是如果元素位於已排序的數組中或者元素不在其中，那麼這種情況會發生更改嗎？我認爲它應該採取較少的搜索來確定該元素不在陣列中，或搜索保持不變

Answer 1

假設您必須在最壞的情況下進行k比較以檢查元素在數組中。在最近的（kth）比較中​​，如果鍵不匹配，則該元素顯然不在數組中。因此，如果元素不在kth之後，則不需要進行任何比較。

因此，最壞的情況應保持不變，不管排序陣列中的元素是否在k=ceil(log(n))。

同樣，在線性搜索的情況下，假設密鑰位於數組的最後位置。我們需要n比較，如果數組的最後一個元素與鍵不匹配，我們可以得出結論，該元素不在數組中。我們不需要再進行比較，最壞的情況將是相同的（在n），而不管陣列中是否存在元素。