線性搜尋(Linear / Sequential Search)& 二元搜尋(Binary Search)


「線性搜尋(Linear / Sequential Search)」與「二元搜尋(Binary Search)」為最基礎、程式碼最簡單的搜尋法,只要學過迴圈(loop)與條件判斷(conditional)就能寫得出來,二元搜尋亦可透過遞迴(recursion)實現。


線性搜尋(linear / sequential search)

使用迴圈,從第一個開始逐一尋找目標值,到下列兩狀況之一時停止搜尋:

  1. 找到目標值。
  2. 搜尋完全部資料仍未找到目標值。

偽代碼&說明

使用單層迴圈,從第一筆資料序找到最後一筆資料,若找到與目標相符者則回傳該筆資料所在位置;若陣列全部找完仍找不到目標資料則回傳 (-1)。

程式碼範例(JavaScript)

function linearSearch(arr,n){
  for(let i=0; i<=arr.length; i++){     //從頭找到尾
    if(arr[i]===n){                     //找到數值與n相符者,回傳其所在索引值
      return i;
    }
  }
  return (-1);                          //全部陣列都找完仍未找到目標資料 => 回傳(-1)
}

時間複雜度

  1. 最糟情況:O(n),即目標值在最後一格,要走過每筆資料才能找到。
  2. 最佳情況:O(1),即目標值在第一格,一找就找到。
  3. 平均情況:O(n/2)=O(n)。

空間複雜度

O(1),僅在原陣列內搜尋,不需額外的空間暫存資料。


二元搜尋(binary search)

僅適用於已經按照大小順序排好的資料,每次搜尋時將資料對半切,看目標值在左半邊或右半邊,直到找到目標值為止。

現假設有一排序好、長度為 8 的陣列 [2,5,7,15,22,35,48,57],要用二元搜尋找到當中的 35。

二元搜尋流程圖(middle的索引值經無條件捨去)
一共只要走 log₂8=3 步,相較之下,使用線性搜尋卻要走五步。

當陣列變得龐大,二元搜尋可省去的步驟數將會相當可觀。例如要在 100,000 筆資料中找到第 50,001 筆資料,使用線性搜尋共要 50,000 個步驟,但二元搜尋只要 log₂100,000=16 個步驟就能找到,兩者的時間複雜度差異十分明顯。

偽代碼&說明

先將陣列兩端分別設為「min」與「max」,並設定中間點為「middle」,為了讓「middle」的值不出現小數點,以便對應陣列索引值,可用「Math.floor()」無條件捨去、「Math.ceiling()」無條件進入、或用「Math.round()」四捨五入,本文以「Math.floor()」無條件捨去為範例。

以已經由小到大排序好的陣列來說,目標值所在位置共有下列三種可能:

  1. 目標值在「middle」與「max」之間:將「middle」設為「min」,改在新的「min」與「max」之間搜尋。
  2. 目標值在「min」與「middle」之間:將「middle」設為「max」,改在新的「min」與「max」之間搜尋。
  3. 目標值就是「middle」:直接回傳「middle」的索引值。

如果全部找完仍無目標值,則回傳 (-1)。

以迴圈實現二元搜尋偽代碼

若使用遞迴法,則透過檢查第「min」項是否跑到第「max」項右邊,確認要找的值「n」是否在陣列中。

以遞迴實現二元搜尋偽代碼
以下列範例來說,若要找的值是不存在於陣列裡的「33」,則第三輪搜尋的「max」變為第 3 項、「min」維持在第 4 項,「max」跑到「max」左方,以上述遞迴法的偽代碼而言,將回傳 (-1)。

以遞迴實現二元搜尋時,處理不存在於陣列中的值之過程

程式碼範例(JavaScript)

//迴圈法
function binarySearchLoop(arr,n){
  let min = 0;                                  //設定最小值min初始位置
  let max = arr.length-1;                       //設定最大值max初始位置
  while(min<=max){
    let middle = Math.floor((min+max)/2);       //設定中間值middle初始位置
    if(n>arr[middle]){                          //情況一:n比middle的值大 => 把min移到middle+1
      min = middle+1;
    } else if(n<arr[middle]){                   //情況二:n比middle的值小 => 把max移到middle-1
      max = middle-1;
    } else {                                    //情況三:n跟middle值相等 => 直接回傳middle,即為目標資料索引值
      return middle;
    }
  }
  return (-1);                                  //全部陣列都找完仍未找到目標資料 => 回傳(-1)
}

//遞迴法
function binarySearchRecursion(arr, min, max, n) {
  if(min>max){                                               //陣列中未有目標資料,max會跑到min左邊 => 回傳(-1)
    return (-1);
  }
  if(arr[max]<arr[min]){                                     //陣列未按照由小到大順序排列 => 回傳false
    return false;
  } else {
    let middle = Math.floor((min+max)/2);                    //設定中間值middle初始位置
    if(n>arr[middle]){                                       //情況一:n比middle的值大 => 下一輪搜尋範圍改從middle+1到max
      return binarySearchRecursion(arr, middle+1, max, n);
    } else if(n<arr[middle]){                                //情況二:n比middle的值小 => 下一輪搜尋範圍改從0到middle-1
      return binarySearchRecursion(arr, 0, middle-1, n); 
    } else {                                                 //情況三:n跟middle值相等 => 直接回傳middle,即為目標資料索引值
      return middle;
    }
  }
}

時間複雜度

  1. 最差情況:O(log n),即目標值在頭尾或緊鄰切第一刀處,要找尋 log₂ n 次,時間複雜度為 O(log₂ n)=O(log n)。
  2. 最佳情況:O(1),即目標資料切第一刀處,一找就找到。
  3. 平均情況:O(log₂ n)=O(log n)。

空間複雜度

視實際執行方式而異:

  1. 迴圈法:O(1),僅在原陣列內劃定範圍並進行比較、搜尋,不需額外儲存空間。
  2. 遞迴法:O(log n),需要額外空間儲存遞迴過程產生的堆疊(stack)。

兩種搜尋法複雜度比較

#演算法 #線性搜尋 #二元搜尋







你可能感興趣的文章

筆記、Command Line Interface

筆記、Command Line Interface

PHP會員管理系統 - 註冊表單判斷

PHP會員管理系統 - 註冊表單判斷

CS50 linked list

CS50 linked list






留言討論