演算法-資料結構學習筆記 Searching Algorithms 搜尋演算法

一、前言

在現實生活中，常常會需要在一個集合裡找出符合條件的資料，例如從一整本學生資料冊裡面找出某位學生的紀錄，或是在商品名錄中找到某項商品。

在網頁或程式的世界裡也是一樣，試著想像一下在 google 的搜尋欄位打上關鍵字後，搜尋引擎是如何在成千上萬筆的網頁資料中，依據我們的瀏覽紀錄、關鍵字和其他資訊去整理出符合條件的結果呢？這背後就是由相當複雜的搜尋演算法完成的。

目前已經有許多演算法用於有效尋找集合中的資料，每個方法有各自適合的情境與限制，本篇會先介紹比較常見的線性搜尋法 (Linear search) 與二元搜尋法 (Binary search)。

二、線性搜尋法

線性搜尋法的概念，就是在一個集合中從頭到尾逐一確認，直到找到目標為止。

在 Javascript 陣列也有內建 indexOf(), find() 和 findIndex() …等，實作這些方法的搜尋演算法，即是所謂的線性搜尋法，會在可迭代的陣列內從頭開始搜尋，直到找到符合條件的目標。

我們可以從下列函式來實作線性搜尋法，函式傳入一個只包含數字的陣列與一個目標數字，並且回傳該目標數字所在的 index 值。

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i
  }
  return -1
}
console.log(linearSearch([1, 2, 4, 7, 10], 7)) // 3

由於會依據資料的數量而呈現線性成長，因此最壞情況的時間複雜度為 O(n)，也就是在陣列的最後一個元素才找到目標；反過來說，如果很幸運地在第一個元素就找到，則時間複雜度為 O(1)。

三、二元搜尋法

相較於上述的線性搜尋法，二元搜尋法則是效率較快的搜尋法，因為它可以一次檢查一半的資料，而不像線性搜尋法只能逐一確認。

假設要在 [1, 2, 4, 7, 10] 找出 7 的位置，二元搜尋法會先從中間的元素下手，也就是 4；接著比對目標數字 7 與目前找到的數字 4，由於 7 大於 4 ，就可以直接去除前半段的元素，專注搜尋後半段的元素，以此類推直到找到目標。

因此，二元搜尋法也有其限制，如果資料的集合不像是上述舉例的陣列那樣依序排列，而是雜亂無章的集合，那就無法使用二元搜尋法了。

我們一樣再用一個函式實作二元搜尋法，函式傳入一個有序排列的數字陣列，以及欲尋找的目標數字，並且回傳目標數字的 index 值，未找到則回傳 -1

function binarySearch(arr, target){
  // set pointer
  let left = 0
  let right = arr.length - 1
  let middle = Math.floor((left + right) / 2)
  
  while (left <= right && arr[middle] !== target) {
    // move pointer and update middle index 
    if (arr[middle] > target) right = middle - 1
    if (arr[middle] < target) left = middle + 1
    middle = Math.floor((left + right) / 2)
  }
  
  return arr[middle] === target ? middle : -1
}
console.log(linearSearch([1, 2, 4, 7, 10], 7)) // 3

二元搜尋法的最佳狀況下，是在第一次的 middle index 就找到目標數字，所以時間複雜度為 O(1)；不過二元搜尋法的優勢在於，它可以一次排除一半的資料，假設今天我要在 8 筆資料裡面找到某一筆，則每次搜尋都可以排除一半的情況下，最慢也只要第三次就可以找到目標 ( 8 > 4 > 2 )，因此其最壞情況的時間複雜度為 O(logN)，比線性搜尋法的 O(n) 還要快。