本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-07-03
在列表中查找数据有两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；二分查找适用于元素已排序的列表。二分查找效率更高，但是你必须在进行查找之前话费额外的时间将列表中的元素排序。
对于查找数据来说，最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表结尾也没有找到。这种方法称为顺序查找，有时也被称为线性查找。它属于暴力查找技巧中的一种，在执行查找时可能会访问到数据结果里的所有元素。
实现起来也很简单，如下：
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === data) {
return true
}
}
return false
}
需要注意的是，这个函数的执行速度是比内置的Array.indexOf() 和 Array.includes() 方法要慢的，这里仅用来掩饰顺序查找是如何运行的。
通常我们会这样在数组中查找最小/大值：
实现起来也很简单：
function findMin(arr) {
var min = arr[0]
for (var i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i]
}
}
return min;
}
function findMax(arr) {
var max = arr[0]
for (var i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i]
}
}
return min;
}
对于未排序的数组，当被查找的数据位于数据集的起始位置时，查找是最快、最成功的。通过将成功找到的元素置于数据集的起始位置，可以保证在以后的操作中该元素能够更快的找到。
该策略背后的理论是：通过将频繁查找的元素置于数据集的起始位置来最小化查找次数。通过多次查找之后，查找最频繁的元素会从原来的位置移动到数据集的起始位置，这就是一个数据自组织的例子：数据的位置并非是由程序员在程序执行之前就组织好的，而是在程序运行过程中由程序自动组织的。
由于对数据的查找遵循“80-20原则”（指对某一数据集执行的80%的查找操作都是对其中20%的数据元素进行查找），因此将你的数据转换成自组织的形式是很有意义的。
修改后包含自组织方式的顺序查找函数实现如下：
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === data) {
if (i > 0) {
// 与前一个元素互换位置
[arr[i], arr[i-1]] = [arr[i-1], arr[i]]
}
return true;
}
}
return false;
}
这种方式可以保证被频繁查找的数据能慢慢向前“冒泡”，也可以保证已经在数据集前面的元素不会被越移越远。
另外一种自组织数据的方式是：将找到的元素移动到数据集的起始位置，但是如果这个元素离起始位置很近，则不会对的它的位置进行交换，要实现这个目标，我们只对距离起始位置在一定范围外的元素进行交换即可，再次参照“80-20原则”，即仅当数据位于数据集的前20%元素之外时，该数据才会被移动到数据集的起始位置。
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === data) {
if (i > arr.length * 0.2) {
[arr[i], arr[0]] = [arr[0], arr[i]]
}
return true;
}
}
return false;
}
如果你要查找的数据是有序的，二分查找算法比顺序查找算法更高效，要理解二分查找算法的原理，可以想象一下你在玩一个猜数字的游戏，这个数字位于1-100之间，而要猜的数字由你的朋友来选定，你每猜一个数字，你的朋友会告知你，你猜的数字是 大于/等于/小于 他选定的数字。所以每次猜中间值是最佳策略。
function binSearch(arr, data) {
var start = 0;
var end = arr.length - 1;
while (start <= end) {
var mid = Math.floor((start + end) / 2); // 中点下标
if (data > arr[mid]) {
start = mid + 1; // 开始指针从mid走到下半区
} else if (data < arr[mid]) {
end = mid - 1; // 结束指针从mid走到上半区
} else {
return mid; // 返回下标
}
}
return -1; // 未查找到
}
如果在数据集中你需要查找的数字是存在多个的，那么该函数返回的下标值会是其中的一个。而由于是一个有序数组，与其重复的值大多在其前后，因此可以增加一个函数用来统计重复值总共有多少个，对应的下标是什么。
实现起来也很简单，就是写两个循环，从已经找到的下标开始分别向前和向后查找，直到找到与当前查找数据不同的数据为止。
function count(arr, data) {
var count = 0;
var indexArr = [];
var position = binSearch(arr, data);
if (position > -1) {
++count; // 找到了其中的一个
indexArr.push(position);
for (var i = position - 1; i > 0; i--) { // 从找到的下标往前查找
if (arr[i] === data) {
++count;
indexArr.push(i);
} else {
break;
}
}
for (var i = position + 1; i < arr.length; i++) { // 从找到的下标往前查找
if (arr[i] === data) {
++count;
indexArr.push(i);
} else {
break;
}
}
}
return {
count,
indexArr
}
}
在这个超高速处理器的时代，除非面向大数据集，否则要测量顺序查找和二分查找耗时上的区别变得越来越困难；然而，处理大数据集时二分查找要比顺序查找速度快，这是由于在决定算法性能的每一步循环嵌套中，二分查找减少了一半的查找量。