搜尋演算法

搜尋演算法（粵讀：sau2 cam4 jin2 syu3 faat3；英文：search algorithm），又或者叫檢索演算法，係指用嚟由數據結構當中搵出一件目標數據嘅演算法。廿一世紀嘅電腦科學界有多種搜尋演算法可以用，而每種都有優缺點。

將手上嘅數據逐個逐個耖，一路耖到搵到想要嗰個為止。

窮舉搜尋

内文：窮舉搜尋

睇埋：線性搜尋

窮舉搜尋（brute-force）係最原始嗰種搜尋演算法，指將手上嘅數據（事先以某啲方式排好咗）逐個逐個耖，一路耖到搵到想要嗰個為止。例如手上有一列以隨機次序排嘅數字，用家想要由呢個數列當中最大嗰個出嚟，用窮舉搜尋嘅話，睇嗰個人就要睇嗮個數列當中嘅每個數字，再俾出最大嗰個出嚟；呢段簡單嘅演算法用粵文寫出嚟嘅話會係：

1. 如果個列入面冇數字，噉就唔會有「最大嗰個數」。
2. 先假定個列入面第一個數字係最大嗰個。
3. 逐個逐個噉去睇個列入面啲數字，如果撞到個數字大過而家手上嗰個「最大數字」嘅話，將新撞到呢個數字設做「最大數字」。
4. 如果睇勻嗮個列入面啲數字嘅話，將手上嗰個「最大數字」交出嚟做答案。

上述呢個演算法用比較形式些少嘅虛擬碼寫出嚟嘅話會係噉：

// Input: A list of numbers L.
// Output: The largest number in the list L.
if L.size = 0 return null;
largest ← L[0];
for each item in L, do
   if item > largest, then
      largest ← item;
   return largest;

// 當中 "←" 代表指定敘述－「A ← B」即係將 A 嘅數值設做 B；
// 而 "return X" 會終止個演算法，並且將 X 嘅數值攞嚟做輸出。

廿一世紀嘅研究者一般都會嫌呢個演算法唔夠好，原因係呢個演算法喺最壞情況（worst-case）嗰陣要睇嗮成個列先至搞得掂，所以又有人諗咗第啲演算法出嚟做呢樣工作－而呢啲新演算法好多時都曉淨係睇個數字列嘅一小部份就經已搵得出想要嗰個數字。

對分檢索

内文：對分檢索

對分檢索（binary search）係用嚟由一個預先排好咗次序（睇排序演算法）嘅數列嗰度搵某一個特定數字出嚟嘅演算法。對分檢索嘅做法係首先將行資料拆做兩橛，再睇吓中間嗰個數係咪等如要搵嗰個數（目標），假如個數列係預先由細到大排好咗嘅話，噉就意味一樣嘢：如果數列中間嗰個數大過個目標，噉個目標實係喺中間個數前面，而如果數列中間嗰個數細過個目標，噉個目標實係喺中間個數後面，跟手段演算法就可以再重複呢個程序，將個搜索範圍縮細，最後搵到個目標嘅數字（假如個目標真係存在喺嗰行數列入面嘅話）。好似係以下呢段虛擬碼噉：

function binary_search(A, n, T):
    L := 0 // 設個數做「左邊界」
    R := n − 1 // 設個數做「右邊界」
    while L <= R:
        m := floor((L + R) / 2) // 將由 L 至 R 嗰段嘢砍兩橛，m 設做中間位
            if A[m] < T: // 如果第 m 個數細過目標（T）嘅話，即係話個目標應該喺第 m 個數後面。 
                L := m + 1
            else if A[m] > T: // 如果第 m 個數細過目標（T）嘅話，即係話個目標應該喺第 m 個數前面。 
                R := m - 1
            else:
                return m // 如果第 m 個數等如目標嘅話，就將嗰個數做輸出。
        return unsuccessful

用對分檢索喺個數列當中搵「7」出嚟嘅圖解；每個箭咀表示一吓耖嘅動作。

對分檢索平均會快過「吓吓都將數列入面嘅數逐個逐個睇一次」嘅窮舉搜尋：喺最壞情況下，想搵嗰個數會係個數列嘅第一個或者最尾嗰個，而喺呢個情況下，用對分檢索嚟做搜尋要做 $O(\log _{2}n)$ 咁多次比較（當中 $n$ 係「個數列入面有幾多個數字」），而「吓吓將數列入面逐個逐個睇一次」喺最壞情況之下就要做 $n$ 次比較，$O(\log _{2}n)$ 數值永遠細過 $n$ 。「由一個數列當中搵一個特定數字出嚟」係電腦好常要做嘅基本作業，如果（例如）喺一個程式當中部電腦要做呢個作業 100 次嘅話，噉一個用對分檢索嘅程式基本上實會快一截，所以編程員多數會比較鍾意用對分檢索。

局部搜尋

内文：局部搜尋

睇埋

• 電腦編程
• 運算複雜度理論
• 蒙地卡羅樹搜尋