Search

在計算機中搜索分為兩種：

      第一種是依次按順序掃一眼，這種方法不僅能夠用於找書，其實在街上找某個地址也是如此。這種方法看似慢，其實是人能夠最快做到的，因為如果隨機亂找，會來回來去找好幾次也不得要領。找東西有經驗的人都知道要按照順序找，找過的地方就要爭取不看第二遍。這也是上帝喜歡笨人的一個很好的例子。這個笨辦法在計算機軟件中還會時不時地用到，我們稱之為順序查找。這是我們今天講的第四個概念，等一會兒我們說說它的應用場景。

      第二種是字典查找法。查字典的人從來不用一頁頁地翻找，而是大約估摸著所要查的字所在的位置，直接打開那一頁，如果發現要找的字在這一頁的前面，就往前翻，否則就往後翻，總之幾次之後，就能找到該找的字。而且愛動腦筋的人在使用一本字典時間長了以後，查字典的速度會提高，用不著翻幾次就能找到想找的字。大家記住這個情況，因為它比絕大多數學計算機的人所了解的二分查找方法更快。

      那麽計算機采用什麽方法呢？上述兩種方法都用，第一種方法顯然是笨辦法，但是在一些場景下依然在使用，比如你在編輯一篇文章時，要把“北京”這個詞挑出來，全都替換成“上海”，除了順序查找別無他法。第二種字典查找法在計算機中用得也很多，但是由於計算機中的字典只有兩個字母，0和1，因此它有了一個新變種，就是計算機從業者常說的二分查找（Binary Search），這是今天介紹的第五個概念。

      關於二分查找的遊戲可能很多讀者朋友都做過。比如遊戲者讓大家在心目中想一個1-1000的數字，然後你問他問題，對方回答“yes（是）”或者“no（不是）”，你用10次一定能夠猜出他心目中想的數字。這個花招其實很簡單，你第一次只要問他是否小於500，如果他給出了肯定的答案，說明數字在1-499裏面，第二次折半問他這個問題即可。類似地，如果他的回答是否定的，說明對方心目中的數字是在500-1000之間，第二次往大了折半問即可。然後你不斷縮小範圍，每次減少一半，這樣問10次即可，因為2的十次方等於1024，大於1000。這就是二分查找。如果你用這個辦法找到數據庫中某個身份證號的位置（以及相應的個人信息），大約只要31次，不需要把13億中國人的身份證掃一遍，31次和13億次，這個差距還是巨大的。

      但是，二分查找有一個問題，就是所有的數據事先要排序，而排序是有成本的。相比查找，排序的速度要慢得多。因此，是否應該對數據先花點時間進行一次排序，則要看具體應用的情況而定。