更多關於二進制搜索的信息

Question

我剛學過二分查找。我搜索了它的用途。

除其他事項外，我發現：

• 可以在Word建議可用於瀏覽器
• 可能在應用Akinator被用來發現你認爲的人？ （不知道http://en.akinator.com/）
• 測試處理器（http://cglab.ca/~morin/misc/arraylayout/）
• 調試

最後三個*我不明白太多。有人可以解釋我嗎？

此外，還有什麼其他用途？

Answer 1

二進制搜索具有O（logn）複雜性....這意味着如果有'n'個已排序元素的列表，則需要logn比較來搜索一個數字。 例如，您的列表包含20個整數：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} ... 而你想搜索這個列表中的任何數字，（想想這個列表中的一個數字）。現在看一下這些組問題：

Q1. Is 10 the number which you chose? - (y/n)? 
-------- if yes then done. (I say "No") 
if no then, 
Q2. Is the number less than 10 - (y/n)? 
-------- I say "No"; which means the number is greater than 10 
Q3. Is 15 the number which you chose? - (y/n)? 
-------- if yes then done. (I say "No") 
Q4. Is the number less than 15? - (y/n)? 
-------- I say "Yes"; So now its sure that the number is in between 10 and 15 (i.e., [11,14]) 
Q5. Is 12 the number which you chose? - (y/n)? 
-------- if yes then done. (I say "No") 
Q6. Is the number greater than 12? - (y/n)? 
I say "Yes"; So now its sure that the number is either 13 or 14 
Q7. Is the number 13? - (y/n)? 
-------- I say "Yes" else its 14. 
(Actually I had chosen 13 as my number) 

So in total there are 20 elements, log of 20 (base 2) is 4.32 ~ 4. 
So here are my comparisons: 
1 st comparison: Is the number less than 10 - (y/n)? 
2 nd comparison: Is the number less than 15? - (y/n)? 
3 rd comparison: Is the number greater than 12? - (y/n)? 
4 th comparison: Is the number 13? - (y/n)? 

，我發現在僅4個比較數13（或14），這是真實的LOGN = log20（基數爲2）= 4。

因此，Akinator應用程序就像這樣工作。它可以處理大量的數據，並根據用戶對Akinator問題的答覆預測答案。 通過決策樹和二進制搜索樹的閱讀可能會幫助你:)