[搜尋演算法]Linear Search — 線性搜尋法

線性搜尋法可以說是最容易理解的搜尋演算法了， 相信大家都有過類似的經驗在圖書館想在在書架上要找一本書”湯姆歷險記” ，假如書本都是未經排序的，就必須一本一本慢慢的找，直到找到要找的書為止，所以以程式碼來說，就會以迴圈遍歷的方式，一步一步的檢查當前的項目是否為要找的對象 ，如果找不到就會回傳 -1。

用 js 實作線性搜尋法

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

幸運的話有可能第一個值就是要找的對象，所以找一次 O(1)就結束了，反之如果運氣不好，目標在最後一個，就要從從頭找到尾 O(n)。

時間複雜度

👍 在最差的情況下，時間複雜度是 O(n)

👎 在最佳的情況下，時間複雜度是 O(1)

🤚 在平均情況下，時間複雜度為 O(n/2)