Linear Search

搜尋演算法 1 – Linear Search / Sequential Search

Linear search (線性搜尋),又稱為 sequential search,是最基本的搜尋演算法,通常用來搜尋尚未排列的資料。

1. Linear Search 原理解釋

Linear search 的原理很直觀:一個一個搜尋,搜尋到目標元素的話就 return,因此時間複雜度是 O(n)。

2. JavaScript 實作

迭代整個陣列,如果有找到目標元素,則 return 目標元素的 index 值,沒有的話則 return -1:

function linearSearch(arr, target) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

3. Time Complexity

最佳:O(1)
最差:O(n)
平均:O(n)

4. 參考資料

大話資料結構(全新彩色版)

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top