查找算法是指从一个集合里比如数组，列表，树里查找我们想要的值。
我们从最简单的线性查找开始。
线性查找，就是遍历集合里的元素，查看是否有和我们想要查找的值相同的，有则查找成功，没有则查找失败。
比如：
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]
线性查找适用于小数据集，没有排序，不需要重复查找，或者我们要查找的数据可能在数据集的开始部分。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。