2
二進制搜索最糟糕的情況是1 + lg n
,但是如果元素位於已排序的數組中或者元素不在其中,那麼這種情況會發生更改嗎?我認爲它應該採取較少的搜索來確定該元素不在陣列中,或搜索保持不變關於二進制搜索中最糟糕的情況
二進制搜索最糟糕的情況是1 + lg n
,但是如果元素位於已排序的數組中或者元素不在其中,那麼這種情況會發生更改嗎?我認爲它應該採取較少的搜索來確定該元素不在陣列中,或搜索保持不變關於二進制搜索中最糟糕的情況
假設您必須在最壞的情況下進行k
比較以檢查元素在數組中。在最近的(kth
)比較中,如果鍵不匹配,則該元素顯然不在數組中。因此,如果元素不在kth
之後,則不需要進行任何比較。
因此,最壞的情況應保持不變,不管排序陣列中的元素是否在k=ceil(log(n))
。
同樣,在線性搜索的情況下,假設密鑰位於數組的最後位置。我們需要n
比較,如果數組的最後一個元素與鍵不匹配,我們可以得出結論,該元素不在數組中。我們不需要再進行比較,最壞的情況將是相同的(在n
),而不管陣列中是否存在元素。
如果您取平均大小寫,則存在差異。但在最壞的情況下,你明確地尋找最長的比較鏈。 – Henry