[数据结构学习笔记16] 线性查找（Linear Search）

查找算法是指从一个集合里比如数组，列表，树里查找我们想要的值。

我们从最简单的线性查找开始。

线性查找，就是遍历集合里的元素，查看是否有和我们想要查找的值相同的，有则查找成功，没有则查找失败。

比如：

5，8，6，9，1，7，3，2，4

我们要找3，那从5开始依次往后，到了第7个（下标6），我们找到了3。如果我们要找10，同样从5开始，依次往后，一直到最后一个元素，都没有10，所以查找不成功。

function linear_search(collectioin, item) {
  for (let i = 0; i < collection.length; i++) {
        if (collection[i] === item) {
             return i;
         }
   }  
   // Item not found
    return -1;
}

调用函数

let data = [5,8,6,9,1,7,3,2,4];
let result = linear_search(data, 3);
console.log(result); // 6
let result1 = linear_search(data, 10);
console.log(result1); // -1

这里有个要注意的，如果有重复的数据在集合里，只返回第一个匹配的下标。

时间复杂度

线性查找的复杂度是O(n)，最好的是O(1)，查找的值正好在第一位，最坏的情况有两种，一种查找的值在最后一位，一种是查找的值不存在。

全局线性搜索，返回所有匹配值，包括重复值。

function global_linear_search(collection, item) {
  let foundPositions = [];

  for (let i = 0; i < collection.length; i++) {
       if (collection[i] === item) {
            foundPositions.push(i);
        }
   }  

   if (foundPositions.length > 0) {
          return foundPositions;
    } else {
         return -1;
    }
}

调用global_linear_search

let data = [5,8,3,9,1,7,3,2,4,3,6];
let result = global_linear_search(data, 3);
console.log(result); // [2,6,9]

线性查找适用于小数据集，没有排序，不需要重复查找，或者我们要查找的数据可能在数据集的开始部分。