「我們是食品監察員。」Frank與Notation警官一邊大步流星地踩著狹窄的跳板上船，一邊喊道。在Frank的示意下，Notation迅速地揮了揮她的工作證，快得根本來不及讓人看清楚證件上寫的是什麼。
「食品監察員？」一位船員疑惑地問道，「我們並沒有運送任何食物啊。」
Frank把這位船員打量了一番，他看起來不像是船長，也不像是被僱傭的保安，他可能只是一位水手，當船長不在的時候就由他負責。這在走私船上很常見，因為如果僱傭安保人員來看守貨物，那會顯得太招搖了。
Frank衝著那位水手吼道：「我們要查查看。我可聽說這條船上有一批腐爛的鰻魚，我就是來查這批鰻魚的。」
「鰻魚？」那位水手對此顯然非常疑惑。
「腐爛的鰻魚！」Frank馬上答道，「我們要到下面去查查。」沒等對方回答，他就朝著艙口大步走去，準備走下甲板。
Notation連忙緊隨其後。
「咱們時間不多，趁著他們船長還沒回來，咱們得趕緊找到這條船的航行日誌。」Frank邊下梯子邊說道，「航行日誌上有貨單，上面會記錄運過的貨物及抵達過的港口。貨單肯定造過假，因為走私船上從來不會記錄真實的貨物。但如果讀得夠仔細的話，我們說不定能發現一些蛛絲馬跡。」
Notation在貨艙後面找到了航行日誌，她把它抽了出來。Frank仔細看了看封面，上面寫著如下信息。
貨單及Retry Loop日誌
船長：A.James
船籍港：Usb
船主：Vinettee家族航運集團有限公司
沒想到在成功避開Vinettee集團圍捕的幾個月後，這次Frank竟然又歪打正著地上了他們的一條船。Frank本能地四處查看貨艙，看有沒有藏起來的黨羽，或改裝成武器的農具，或者有沒有鼻涕蟲比賽的痕跡。Frank打消了最後一種想法的可能性，因為大家都知道鼻涕蟲不會在船上賽跑，它們好像不喜歡在滿是鹽水的環境裡賽跑。
他搖搖頭，繼續把注意力集中到眼前的問題上。Frank必須在Vinettee集團的人得知他上船之前找到點線索，不然他有可能又下不了船了。他立即把航行日誌翻到最後一頁，然後開始一頁一頁往前翻。
Notation問道：「你在做什麼？」
「我在找最後一次的航行日誌記錄。」Frank回答。
「一頁一頁地找？」Notation問道，「這本日誌一共有1000頁，為什麼你不使用二分搜索的方法？就是我們在兩分鐘之前剛剛使用過的方法。」
Frank停了下來。雖然他並不是尋找某個特定頁碼，但是他仍然可以使用二分搜索的方法找到這條船的最後一次航行日誌。他可以根據當前頁是否有文字記錄來減少搜索範圍。
「好的。那就使用二分搜索的方法。」Frank同意了。
Frank再次打開航行日誌，並翻到最後一頁。在確定這本日誌正好1000頁後，他設定這本日誌的頁碼下界為1，上界為1000。他得出中間值是500，然後翻到了第500頁。
他發現第500頁和501頁都是空白，因此Frank知道了這本航行日誌的最後一次航行記錄必然在第499頁或之前。現在他把第499頁設為新的上界值。然後再次算出中間值為250，並翻到第250頁。他發現第250頁竟然又是空白。
「這看起來像一本新的日誌啊。」Notation說，「還好你剛才沒有從最後一頁一頁往前翻。」
此時，Frank根本沒空理她。他再把下界值設為1，上界值設為249，並算出中間值125，並立馬翻到了125頁。這次他找到了筆跡，由此可以斷定，最後一次航行日誌的記錄必然在125頁之後，因此他將下界值調整到125。最後一條記錄必然在125~249頁之間。
「187頁！」在Frank在腦海裡計算出中間值之前，Notation便脫口而出。Frank翻到了第187頁，發現這頁也有文字記錄，看來187頁也不是最後一次航行記錄，應該還在187~249頁之間。於是他繼續調整下界值為187。
「218頁！」Notation說道。該頁竟然還是空白頁，那麼最後一條記錄必然在187~217頁之間了，因此Frank將下界值和上界值分別改為187和217。
「202頁！」在Frank將上下界值相加之前，還沒來得及計算中間值，Notation又脫口而出。
「你為什麼算得這麼快？」Frank問道。
「熟能生巧唄。」她回答，「在學校裡，每當課餘休息時我們都會做二分搜索，我總是能贏。」
Frank搖搖頭，咕噥道：「聽起來挺好玩的。」
Frank翻到了第202頁和203頁，發現也都有筆記。「接下來是210頁！」Notation說道。
在第210頁，他們終於發現這是航行日誌的最後一頁，上面描述了的最後一次航行的詳細記錄。「接下來做什麼？」Notation問道。
「我們要找到最後一次航行中可疑的包裹或者是港口。這頁大約有70個記錄，我們要一條一條地看。」
「窮舉搜索？」Notation問道，「我們難道不能用一種更高效的方法嗎？難道不能把這些記錄按照裝卸貨和交付時間來排序嗎？」
「這裡不能使用排序。」Frank回答道，「我們不知道每條記錄的時間。只有當使用了確定的維度將這些數據排序時，這些排好序的數據才有用。不能按照不確定的維度來進行排序。你想想是不是這樣？」
「哦。這是『天氣記錄』問題。」Notation說。
「什麼問題？」Frank問道。
「這是一個在查找過程中以錯誤的方法對數據進行排序的例子。」Notation解釋道，「Drecker教授給我們舉了一個例子：如何在最近十年中找到最冷的一天。如果你將每天的氣溫日誌按照日期時間來排序，你使用二分搜索可以很容易地知道一個指定日期的天氣記錄。但是這並不能幫助我們找出最冷的一天，所以我們仍然需要瀏覽每一天的氣溫記錄。」
「我們還是回到現實吧！」Frank說道，「別說那些沒有用的，此時你還是找出哪些記錄對你有用，哪些對你沒有用吧。不要擔心，剛才的錯誤對一個新手來說是很常見的。」
Frank看到Notation對他的話大為惱怒，不禁竊喜，並竭力控制住自己的幸災樂禍。每個新手在剛出校門時都認為自己無所不知，但是事實證明每個人都還有許多東西需要學習。這次幸好Notation並沒有遇到太多麻煩。Frank之前曾經花費很長時間用鏟子去鏟成桶的豬糞，也正是那個時候，他瞭解到了二分搜索，那時他也對他的職業選擇產生了質疑。
大約三分鐘後，他們找出了唯一的線索。Retry Loop最近有兩次可疑的停靠，Mudwall港口和Frayed Cable島。即使是走私人員，停在這兩個地方也非常奇怪。Mudwall港口依托一個偏遠又滿是泥漿的農場，還經常吹噓其少之又少的貿易量。Frayed Cable島更加荒涼：這是一座岩石小島，島上僅有一座建築——現在已經廢棄的IronRing監獄。
「這裡，」Frank指著日誌說道，「這就是他們拿走你文件的地方。Mudwall港口或Frayed Cable島。他們可能在一個地方丟掉文件後在另外一個地方提取款項。」
「你怎麼知道的？」Notation問道，她看起來很懷疑，「難道我們不應該考慮所有港口……」
Frank打斷她的話：「我們沒有時間找出所有港口。」他沒有詳細解釋。他使用他自己發明的算法，即啟髮式搜索，雖然在當船長時這種算法曾讓他陷入麻煩，但是他有一種直覺，並且他堅信這種直覺。
「你確定……」Notation正要問，但是被他們上方的聲音打斷了。
Frank沒有說話，但是可以很清楚地認出這聲音。麻煩來了。
警用算法導論：二分搜索Ⅱ
節選自Drecker教授講義
使某個算法有效的關鍵因素是信息。對於二分搜索，我們得瞭解有待排序的數據的相關信息，以便知道數據是按照什麼方式排序的。為了排除（或縮小）較大查找範圍，所使用的算法必須能夠保證我們要找的目標值不在被去除的範圍內。
但是，按照某個維度對數據排序後，並不意味著你可以按照另一個維度對數據進行二分搜索。例如，你正在查找某個記賬單，以便找出線索。記賬單是使用交易號來排序的，這表明交易被按照記錄時間來排序了。這意味著每個條目的交易號都小於其後麵條目的交易號。如果當前條目的交易號為105，則這個條目之前的所有條目的交易號都小於105，其之後的所有條目的交易號都大於105。
但是，這也意味著條目的其他字段（如交易的實際日期、交易者姓名或交易金額）並未按一定的順序排列。如果你想要找出特定可疑金額的對應交易或者使用已知軍火商找出相關交易，要怎麼辦呢？這時現有的排序是否有用？沒用，你需要使用詳盡的線性查找。
雖然你知道Zed咖啡館發生了編號為105的交易，但是這並不能讓你知道該場交易前後的交易的交易者信息或交易金額。
同樣道理，如果你按照交易金額遞增的順序來排列賬目，則可以快速找出所有價值為250美元的交易，但是這並不能幫助你找出特定的交易日期、交易號或交易者姓名。
1 鼻涕蟲遇到鹽就會化成水你信不信？請移步這裡http://www.ahalei.com/thread-9150-1-1.html，友情提示畫面太美哦——譯者注返回