05. 搜索演算法

電腦常需要在大量的資料集之中尋找資訊，因此電腦必須為此發展出快速又有效的方法。

以下透過一些活動來推演三種不同的搜尋方式：線性搜尋法、二分搜尋法以及雜湊搜尋法。

【暖身活動 - 傳統海戰棋】

遊戲人數：2人

工具：每人一張紙，上面有兩組6x6的座標方格，第一組稱為佈局盤、第二組稱為炮擊盤，如圖所示

1. 佈局：

遊戲開始前，雙方在版面上放置共計四艘的船艦，分別是佔五格的航空母艦（以字母Ａ表示）、佔四格的戰艦（以字母Ｂ表示）、佔三格的巡洋艦（以字母Ｃ表示）、以及佔兩格的巡邏艇（以字母Ｄ表示）

佈局結果舉例如下

2. 炮擊開始：

雙方玩家輪流進行，一次喊出一個位址作為炮擊地點。

若對方棋盤上所對應的位置有船艦，則需說出被擊中的船艦代號並在己方的佈局盤上的對應位置打叉，猜測方則根據回應在炮擊盤上的猜測位置記錄擊中的代號；

若對方棋盤上所對應的位置沒有船艦，對方則說「ＭＩＳＳ！」，猜測方則在炮擊盤上的猜測位置上寫下「╳」，被攻擊方則在此位置上寫下「○」。

遊戲進行示例：

【回合一 – 玩家１炮擊位置３Ｂ，結果為ＭＩＳＳ，進行後棋盤記錄如下】

【回合二 – 玩家２炮擊位置４Ｃ，結果為擊中船艦代號Ｃ，進行後棋盤記錄如下】

【回合三 – 玩家１炮擊位置１Ｄ，結果為擊中船艦代號Ａ，進行後棋盤記錄如下】

2. 遊戲結束條件：

其中一方的炮擊盤上寫滿5個A、4個B、3個C及2個D（亦即對方的佈局盤上所有的船艦都已被打叉）。

【正式活動 - 程式海戰棋】

海戰棋遊戲連結：

http://bk.chjh.hc.edu.tw/html5/html5_battleships/battleships.html

遊戲總共有六個關卡，目標是藉由搜尋策略，找出目標的船隻編號，並用飛彈將之擊沉。

1. 線性搜尋法（linear search或稱sequential search）：

編號隨機排列，搜尋時除了憑空猜測之外，只要一個接一個走訪所有的位置，一定可以找到目標。

2. 二分搜尋法（binary search）：

先將編號按照大小順序排列，每次猜測時都將目標範圍縮小一半，如此可快速鎖定範圍。

3. 雜湊搜尋法（hashing search）：

編號已按照特定規則進行分組，只要知道分組的位置，就能馬上縮小搜尋的範圍。

二分搜尋法比線性搜尋法快，但線性搜尋法不需要照順序排列編號的時間。

雜湊搜尋法通常來說會比其他兩種快，但也有可能會變得非常慢。在最糟的情況下，如果所有船都同在一個船泊，那就會變得和線性搜尋法一樣慢了。

電腦儲存了大量資訊，它們必須要能夠快速對其進行搜尋篩選。而搜尋引擎所面對的世界上最大搜尋問題之一，就是他們必須要在極短時間內搜尋數十億個網頁。

而電腦被要求尋找的資料，像是文字、條碼編號或是作者名稱等，則被稱為「搜尋關鍵字」。

電腦可以非常快速的處理資訊，而你可能會認為為了找到想要的資訊，它們必須從頭開始，直到找到想找的目標為止。

這是我們在前兩關進行「線性搜尋」中所使用的方法。但這種方法即使對電腦而言也過於緩慢了。

舉個例子，假設一間超級市場的貨架上有一萬種不同產品，當櫃檯掃描一個條碼時，電腦必須最多搜尋到第一萬次才能找到產品的名稱與價格。這樣即使檢查每筆條碼只花千分之一秒，檢查完所有條碼也要花10秒。想像一下，要花多少時間才能掃描完一個家庭會採買的林林總總的雜貨。

二分搜尋法看起來是比較好的方式。二分搜尋法中，先將每筆數字照順序排列，然後檢查列表中間的項目，就可以知道要找的關鍵字是在列表前半還是後半。接著重複該動作，直到找到要搜尋的項目為止。舉剛才超級市場的例子，一萬個項目最多需要進行十四次檢查，也就是大約兩百分之一秒，幾乎是一瞬間即可完成搜尋。

第三個尋找資料的方法叫做雜湊。在這種方法中，關鍵字本身會直接指示到哪裡找到這個資訊。舉個例子，假設要搜尋電話號碼，你可以將所有數字加起來，然後除以11前取餘數。這個做法得到的雜湊關鍵字有點類似先前在錯誤檢查、修正的單元中所提到的同位檢查數字。用這種方法，通常電腦可以很直接地找到要搜尋的資訊。不過還是有小部份的可能，在同一個位置有好幾筆資料，而電腦必須在這幾筆裡面再繼續搜尋。