演算法筆記-搜尋

  • 又稱為循序搜尋(Sequential Search)

說明

  • 是最簡單的搜尋法
  • 原理是在資料列中從頭開始逐一的搜尋，一筆一筆的資料值與搜尋目標值做比對，直到找到為止
  • 時間複雜度：O(n)

步驟

  1. 使用for迴圈，把目標數和陣列中的數一個一個比較
  2. 如果找到，就停止迴圈
  3. 如果全部比對完仍沒有找到，回傳-1，表示目標元素不存在於陣列中

範例

const numbers = [1, 3, 5, 7, 9, 12, 15, 18. 21, 24]function linearSearch(arr, n){    for(let i = 0; i < arr.length; i++){    if(arr[i] === n){            console.log('找到n了')            return        }    }    console.log('沒有找到n')    return -1 }linearSearch(numbers, 21)

說明

  • 當資料已經是排列好的狀態
  • 在已排序好的資料列中找出中間值，再將搜尋的目標值與中間值作比較
  • 如果目標值小於中間值，則往左邊資料列尋找
  • 如果目標值大於中間值，則往右邊資料列尋找
  • 時間複雜度：O(log n)

步驟

  1. 先把陣列中的第一個數（left） 和最後一個數（right）的Index拿出來
  2. 當left <= right的時候，代表還沒找到目標值
  3. 以這兩個數來取中間值 (middle)
  4. 把目標值和中間值比對
    • 大於中間值：如果 n 大於 arr[middle]，則 n 只可能存在於 middle 之後的部分
    • 將 min 設為 middle + 1
    • 小於中間值：如果 n 小於 arr[middle]，則 n 只可能存在於 middle 之前的部分
    • 將max 設為 middle - 1
    • 等於中間值：如果 n 等於 arr[middle]，則已經找到了目標元素，返回 middle
  5. 繼續重複2~4步驟，直到 left <= max 為止
  6. 如果迴圈結束還沒有找到目標元素，那麼回傳 -1，表示目標元素不存在於陣列中

範例

const numbers = [2, 4, 6, 8, 10, 122, 144, 166, 188, 200, 220, 240, 280]function binarySearch(arr, n){    let min = 0    let max = arr.length - 1        while(min <= max) {        let middle = Math.floor((max + min)/ 2 )            if(n > arr[middle]){            min = middle + 1        }else if (n < arr[middle]){            max = middle - 1        }else if (n === arr[middle])             {            return middle           }       }    return -1}console.log(binarySearch(numbers, 122)); // 5console.log(binarySearch(numbers, 7)); // -1

備註

  • 設定迴圈條件 left <= right ，是因為可能陣列中只有一個數字的狀況
  • 範例
const arr = [6]left = 0right = 0 // 如果設定 right < left 會回傳-1，導致結果錯誤

說明

  • 是應用Binary Search的搜尋方法
  • 先找出一個範圍，使目標值落在這個範圍內，然後在該範圍內使用Binary Search
  • 主要用在搜尋無限、無邊界的已排序序列 （資料數量很大時使用）
  • 從底數為 2，指數為 0 的索引（20）開始，不斷比較在 21, 22 直到 2n 位置上的值
  • 若比目標值大，停止指數成長，直接從該位置執行Binary Search，回頭尋找目標值
  • 時間複雜度：O(log n)

步驟

  1. 宣告一個變數i，初始值為 1
  2. 在 while 迴圈中，不斷地將 i 值翻倍，直到這個範圍的最大值大於或等於目標值
  3. 在找到的範圍中，執行Binary Search

寫法

// Binary Searchfunction binarySearch(arr, target, start, end) {  while (start <= end) {    const mid = Math.floor((start + end) / 2);    if (arr[mid] === target) return mid;    if (arr[mid] < target) start = mid + 1;    else {        end = mid - 1    };  }  return -1;}function exponentialSearch(arr, target) {  if (arr[0] === target) return 0;     // 找出目標可能在的範圍  let i = 1;  while (i < arr.length && arr[i] <= target) {    i *= 2;  }    // 確定範圍後，使用Binary Search  return binarySearch(arr, target, i / 2, Math.min(i, arr.length - 1));}

範例

數列：1, 5, 6, 77, 88, 99, 666, 777, 888, 999, 1111, 2222 目標：666

  1. 2 0 = 1, arr1 = 5, 5 < 666, i+1
  2. 21 = 2, arr2 = 6, 6 < 666, i+1
  3. 22= 4, arr4 = 88, 88 < 666, i+1
  4. 23 = 8, arr8 = 888, 888 > 666, 停止
  5. 把24 ~ 28之間的數拿出來 88, 99, 666, 777, 888
  6. 執行Binary Search搜尋

參考資料

# Alogorithm # Search