編程珍珠問題：在二進制搜索中檢查排序數組

在Programming Pearls（第二版）第5列中，問題5的問題是關於在未排序的數組上執行二進制搜索。編程珍珠問題：在二進制搜索中檢查排序數組

你怎麼能部分檢查添加到功能在顯著少比爲O（n-1）費用？

我知道你可以檢查每次迭代並達到O（log n），但後面的提示表明有一個O（1）解決方案。

這是什麼解決方案？

2010-09-15 Hortitude

稍微詳細一點？ – pavanlimo 2010-09-15 04:39:03

摘要

部分檢查，如果該陣列被排序，使得二進制搜索可應用於可以在O完成（log n）的，作爲所述OP，並且在O（1）。 O（log n）方法是針對以前的探針檢查每個探針，以確保它比較正確（小於，大於）。 O（1）方法只是檢查通過二進制搜索找到的最後一個元素和其旁邊的元素，以便如果找不到所需的元素，則至少找到正確的插入位置。如果尋找到的元素被發現，那麼這是一個很好的O（1）部分檢查。

較長的解釋

碼塊之前問題的部分表示，一個共同的問題是使用排序的數組上二進制搜索。基本上，如何使用部分檢查來檢查數組是否以小於O（n-1）的成本排序？ O（log n）解決方案是檢查每個二進制搜索探針網格相對於前一個探針（小於或大於它預期的）。這並不保證數組是排序的，但它是一個很好的部分檢查。

我能想到的唯一的O（1）檢查就是檢查搜索到的最終位置，使得它的值和相鄰值與搜索元素應該位於何處的想法相匹配，即使元素沒有找到。這是一個非常好的部分檢查：如果找到元素，那麼事情可能正常工作。如果不是，那麼檢查它應該在哪裏的元素，使得有一個小於搜索的元素，然後是一個大於搜索的元素的元素。但是，我意識到以這種方式檢查意味着二進制搜索O（log n）已經完成，所以我不知道這是否是真正的O（1）。但是，它僅將O（1）添加到整體搜索中，所以我認爲它是適用的。

來源

2010-09-15 05:07:13

寫得很好。我想知道這是否可能是解決方案，但對我而言，簡單地檢查最終結果會讓您檢查數組是否已排序，這似乎有點奇怪。這實際上做的是檢查當你完成後你處於微觀有效狀態。它仍然有可能發現自己在一個本地元素排序的山谷中，但是您搜索的元素在其他地方未排序：[1,2,4,5,6,7,3,10]如果您搜索3你會認爲這是排序，並不會找到[3] – Hortitude 2010-09-15 16:34:54

是的，這就是爲什麼它被稱爲部分檢查。它不能保證數組是排序的，但它可能是。只有完全檢查的方法是線性方法，但部分檢查也可以。 – 2010-09-15 21:23:56

編程珍珠問題：在二進制搜索中檢查排序數組

回答

相關問題