線性搜索,也被稱為順序搜索或簡單搜索,是最基本的搜索演算法。給定一個資料結構,例如一個數組,我們通過查看所有元素來搜索某個項目,直到找到為止。

它的實現非常簡單:

const linearSearch = (list, item) => {
  for (const [i, element] of list.entries()) {
    if (element === item) {
      return i;
    }
  }
};

這會返回我們要查找的項目的索引。例如:

linearSearch(['a', 'b', 'c', 'd'], 'd'); //3(索引從0開始)

如果我們查找的是’a’,該演算法只會查看第一個元素並返回,所以速度非常快。

但是如果我們查找的是最後一個元素,該演算法需要遍歷整個數組。計算大O值時,我們始終考慮最壞情況。

因此,該演算法的時間複雜度(演算法複雜度)為O(n)。