問題是這樣的：有一個有n個數字的排序列表。給定x，在排序列表中找到一個等於x的數字。這裏我們假設x確實在列表中。有一個oracle可以對你的問題回答「是」或「否」「是否x> = y？」。與普通的二分查找不同，oracle允許對你的問題說謊一次。解決這個問題的最幼稚的方法是你向每一個問題提出兩個問題。如果兩個答案是一樣的，你就知道奧拉爾沒有說謊。這個算法我們需要比較2log_2（n）次。但是這個問題要求我找到一個只使用log_2（n）+ o（logn）比較就能找到x的算法。如何在一個謊言模型中進行二進制搜索？
我非常努力，但失敗了。任何人都可以給我一些關於如何解決這個問題的建議嗎？謝謝。
記錄您所處的時間間隔。如果您需要總共k個問題，請每sqrt(k)步驟檢查一致性（無論您是否處於您應該達到的時間間隔內）。在檢查一致性時，你可能會問每個問題兩次以確定。如果您檢測到不一致，請返回sqrt(k)步驟。你會問更多的問題c*sqrt(k)。
我想你說出一個解決這類問題的一般方法。 sqrt（k）只是一種可能的方式。可能是日誌（k）也可以提供幫助。重要的是你必須重新檢查o（k）個步驟。那麼算法最終會給你k + o（k）的複雜性。 – 2012-01-30 16:11:01
呵呵，我認爲n.m意味着k個問題，而不是排序列表的長度。在這裏我們需要logn的問題，所以k = O（logn）。 – 2012-01-30 17:04:01
@ hhn007：確切地說，k個問題。爲什麼sqrt（k）？因爲如果你檢查每一個步驟，你可能會詢問t或大約k/t個額外的問題，這取決於oracle是位於開始位置還是靠近結束位置。爲了保證t和k/t都很小，你需要使它們相等。 – 2012-01-30 19:11:49
只問甲骨文這個問題：「是x> = y？」一次在你的二進制搜索的每次迭代。 如果你兩次得到相同的答案，那麼你知道oracle並沒有第一次說謊。
例如，您正在搜索x = 1，並且您測試的第一個測試針對y = a，並且oracle回答x < a。在第二個測試中，您針對y = b進行測試，並且oracle回答x < b。由於您使用的是二分查找，並且oracle說'<'，並且數組已排序，所以您知道b < a。因此，如果你還知道一個x，那麼第一個答案就不是謊言。如果第二個答案是謊言，並且x> b，那麼它仍然是真的，因爲甲骨文只能說謊一次。
即使答案不回來，情況也是如此。例如，您得到三個答案：x < a，x> = b，x < c，您知道c < a，通過您的二分查找，所以它一定是真的，即x < a，而oracle不是當他告訴你時說謊。
那麼當oracle確實說謊時會發生什麼？如果謊言是x < y，那麼事實是x> = y。因此，當您繼續進行二分法搜索時，從這一點開始，您檢查的數字將會過小，並且答案將始終爲「> =」，直到您到達二分查找的底部。此時，你意識到如果甲骨文謊言，他最後一次告訴你「」=「以外的東西。所以，你在甲骨文騙你的地方重新開始你的二分查找，並說「x < y」。
這將始終使用< 2 log_2 n比較，但是如果oracle在搜索開始時對你有用，那麼你將不得不重複近log_2 n工作，所以你不會得到log_2 n + o （日誌n）答案你正在尋找。因此，你應該納入nm提出的想法，如果你得到相同的答案，連續說sqrt（log n）次，那麼你懷疑oracle可能對你撒謊了，你立即重新提出你的問題在答案開始重複之前詢問，而不是等到二進制搜索的底部。遵循這個策略，在最壞的情況下，您將重新提出一個問題記錄n/sqrt（log n）次，並且您將始終捕獲最多sqrt（log n）浪費工作的謊言，從而實現您的運行時間尋找。
你可能想改變這個工作了經典二進制搜索，怎麼樣試着問了Oracle在每次迭代中比較數組，而不是2個不同勢指標只是1，是這樣的：
assume Oracle(x,y) returns "x>=y?", assume every division is returning floor integer.
LyingOracleSearch(A,n,toFind)
1. if (n==0) return not found
2. if (A[0]==toFind) return found
3. if (Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then
4. return LyingOracleSearch(A[(n/4)...(3n/4)],3n/4-n/4,toFind)
5. if (Oracle(A[n/4],toFind) and !Oracle(toFind,A[3n/4]) then
6. return LyingOracleSearch(A[0...(n/4)],n/4,toFind)
7. if (!Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then
8. return LyingOracleSearch(A[(3n/4)...n],n-3n/4,toFind)
9. return LyingOracleSearch(A,n,toFind); \\orcale lied!
我認爲，它可能是錯誤的壽。
它的複雜度與原始BS相同，但是最好再問兩次或更多。注意一個元素從來沒有被比較過兩次，除非oracle存在，所以如果它存在一次甚至k次，其中k很小 - o（logn），那麼我們很好。
你可以去你最喜歡的編碼環境，並嘗試編碼它，每次做比較，數一數。試試這個和天真的，並比較結果，如果我沒有錯，天真應該比這兩倍。
請注意，我並不太在意索引，你需要做一些思考，以確保我沒有錯過索引或沒有重複索引意外。
不錯的主意。然而，你能保證你的算法比天真的二進制搜索更好嗎（每次問兩次）？我也嘗試了很多方法來劃分列表，並構造一個存在的三個索引：「oracle說x是內部的」，第二個「oracle說x一次在外面」，第三個「oracle說x是外面它兩次「。然後我可以扔掉第三個元素。但是，該算法似乎在第一步之後起作用。編輯 – 2012-01-30 16:07:19
，看看你是否明白。 – 2012-01-30 16:43:17
好的，我會嘗試。不管怎麼說，還是要謝謝你。 – 2012-01-30 17:05:10
使用事實，在甲骨文撒謊後，二進制搜索出錯的方式，並且自那時以來（在任何情況下，始終爲>=或始終爲<），oracle的答案都沒有變化。如果在oracle的log(log(n))步驟的答案中沒有更改，請檢查時間間隔一致性。如果當前時間間隔不一致，再次詢問oracle，如果仍然不一致，請返回log(log(n)) + 1步驟並繼續進行正常的二分查找。
此過程需要O(log(log(n)))平均一致性檢查和最多log(log(n))其他二進制搜索步驟。
其他問題的平均數是c*log(log(n))，其他問題的最大數量是log(n)/(log(log(n))) + log(log(n))。
很好。我想你是對的。我還注意到，當甲骨文告訴你一個謊言後，它總是會給你同樣的方向。在log（log（n））步驟後檢查一致性是很聰明的。但是爲什麼你在log（log（n））之前加2？爲什麼不只是登錄（日誌（n））？因爲最多隻有log（n）/ log（log（n））次才能檢查。可能是指log（n）/ log（log（n））+ log（log（n））作爲額外問題的最大數量？ – 2012-01-30 16:00:42
對，它會與'log（log（n））'一起工作。 – 2012-01-30 16:44:57
我猜想在3 * log(n)解決這個問題可以很容易，通過在每一步問三次不等式問題，決定是最主要的。
'2 * log_2（N）'和'log_2（n）+ O（log（N））'都是'O（log（N））'。隱藏的常量可以用來改變日誌的基礎。你確定這些是解決方案標準嗎？ – phs 2012-01-30 02:35:49
好的。複雜性是相同的，即O（log（N））。你是對的。然而，這個問題希望我找到一個只需要log_2（n）+ o（logn）比較的算法。這在天真二進制搜索中比2 * log_2（n）的比較少得多，每次問兩次。我很抱歉，我沒有把這個問題弄清楚。 – 2012-01-30 02:48:35
請注意，如果其中一個答案是謊言，你需要問三次才能發現正確的答案。 – OleGG 2012-01-30 03:10:57