線性搜尋（Linear / Sequential Search）& 二元搜尋（Binary Search）

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

線性搜尋（linear / sequential search）

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

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

偽代碼&說明

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

程式碼範例（JavaScript）

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

時間複雜度

最糟情況：O(n)，即目標值在最後一格，要走過每筆資料才能找到。
最佳情況：O(1)，即目標值在第一格，一找就找到。
平均情況：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()」無條件捨去為範例。

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

目標值在「middle」與「max」之間：將「middle」設為「min」，改在新的「min」與「max」之間搜尋。
目標值在「min」與「middle」之間：將「middle」設為「max」，改在新的「min」與「max」之間搜尋。
目標值就是「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;
    }
  }
}

時間複雜度

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

空間複雜度

視實際執行方式而異：

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

線性搜尋（Linear / Sequential Search）& 二元搜尋（Binary Search）