检索算法

本章介绍了数据检索的一个方面: 如何在列表中查找特定的值。

在列表中查找数据有两种方式: 顺序查找和二分查找。

顺序查找适用于元素随机排列的列表;
二分查找适用于元素已排序的列表。

二分查找效率更高，但是你必须在进行查找之前花费额外的时间将列表中的元素排序。

顺序查找

对于查找数据来说，最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表结尾也没有找到。这种方法称为顺序查找，有时也被称为线性查找。它属于暴力查找技巧的一种，在执行查找时可能会访问到数据结构里的所有元素。

顺序查找的实现： 只要从列表的第一个元素开始循环，然后逐个与要查找的数据进行比较。如果匹配到了，则结束查找。如果到了列表的结尾也没有匹配到，那么这个数据就不存在于这个列表中。

代码实现：

function seqSearch(arr, data) {
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            return i;
        }
    }
    return -1;
}

如果在数组中找到了参数 data，返回所在的位置，如果没有找到要查找的数据，函数返回-1。

seqSearch() 函数的执行速度比内置的 Array.indexof() 方法慢，这里仅用来演示顺序查找是如何运行的。

查找最小值和最大值

查找最小值

首先看看如何在数组中查找最小值，算法如下。

将数组第一个元素赋值给一个变量，把这个变量作为最小值。
开始遍历数组，从第二个元素开始依次同当前最小值进行比较。
如果当前元素数值小于当前最小值，则将当前元素设为新的最小值。
移动到下一个元素，并且重复步骤 3。
当程序结束时，这个变量中存储的就是最小值。

代码实现如下：

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 max; 
}

实例化个例子：

var nums = [];
for (var i = 0; i < 100; ++i) {
  nums[i] = Math.floor(Math.random() * 101);
}

document.getElementById('box').innerHTML = nums;

var minValue = this.findMin(nums); 
var maxValue = this.findMax(nums); 

document.write("最小值是:" + minValue + '<br />');
document.write("最小值是:" + maxValue);

使用自组织数据

对于未排序的数据集来说，当被查找的数据位于数据集的起始位置时，查找是最快、最成功的。通过将成功找到的元素置于数据集的起始位置，可以保证在以后的操作中该元素能被更快地查找到。

通过将频繁查找到的元素置于数据集的起始位置来最小化查找次数，这就叫做自组织数据。

由于对数据的查找遵循“80-20 原则”，因此将你的数据转化为自组织的形式是很有意义的。

“80-20 原则”是指对某一数据集执行的 80% 的查找操作都是对其中 20% 的数据元素进行查找。自组织的方式最终会把这 20% 的数据置于数据集的起始位置，这样便可以通过一个简单的顺序查找快速找到它们。

举个例子，理解对 seqSearch() 函数进行改动以加入自组织方式

var numbers = [5,1,7,4,2,10,9,3,6,8];

//改动后的seqSearch() 函数
function seqSearch(arr,data) {
    for(var i = 0; i < arr.length; ++i) {
        if(arr[i] === data) {
            if( i > 0) {
                swap(arr,i,i-1);
            }
            return true;
        }
    }
    return false;
}
 
//swap() 函数来对这次找到的数据与当前存储在上一个位置的数据进行互换。
function swap(arr,index,index1) {
    temp = arr[index];
    arr[index] = arr[index1];
    arr[index1] = temp;
}

for (var i = 0; i <= 5; i++) {
  seqSearch(numbers, 4);
  console.log(numbers);
}

这种写法同时可以保证已经在数据集前面的元素不会被越移越远。

二分查找

如果你要查找的数据是有序的，二分查找算法比顺序查找算法更高效。

var nums = [0,5,46,85,102,212,503];  //必须先排序好
 
function binSearch(arr,data) {
    var upperBound = arr.length - 1;
        lowerBound = 0;
    while(lowerBound <= upperBound) {
        var mid = Math.floor((upperBound + lowerBound) / 2);
        console.log('此时的中点：' + mid);
        if(arr[mid] < data) {
            lowerBound = mid + 1;
        } else if(arr[mid] > data) {
            upperBound = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

console.log(binSearch(nums,46));

计算重复次数

count函数一开始调用 binSearch() 函数来查找指定的值。如果在数据集中能找到这个值，那么这个函数将开始通过两个循环来统计这个值出现的次数。第一个循环向下遍历数组，统计找到的值出现的次数，当下一个值与要查找的值不匹配时则停止计数。第二个循环向上遍历数组，统计找到的值出现的次数，当下一个值与要查找的值不匹配时则停止计数。

function count(arr,data) {
    var count = 0,
        position = binSearch(arr,data);
        if(position > -1) {
            ++count;
            for(var i = position-1; i > 0; --i) {
                if(arr[i] === data) {
                    ++count;
                } else {
                    break;
                }
            }
            for(var i = position + 1; i < arr.length; ++i) {
                if(arr[i] === data) {
                    ++count;
                } else {
                    break;
                }
            }
        }
        return count;
}