读【数据结构与算法】之检索算法
本文只包含数据检索的一个方面：如果在列表中查找特定的值。
在列表中查找数据有两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；二分查找适用于元素已经排列的列表。二分查找效率高，但是必须在查找之前话费额外的时间将列表中元素排序。
顺序查找
顺序查找也被称为线性查找。顺序查找的实现很简单，就是从列表的第一个元素开始循环，然后逐个与要查找的数据进行比较。如果匹配到了，则结束查找。
简单实现：
/**
* 顺序查找数组中数据
* @param {Array} ary 数组
* @param {Any} data 要查找数据
* @return {Number} 数据在数组中位置
*/
function seqSearch(ary, data) {
for (var i = 0, len = ary.length; i < len; i++) {
if (ary[i] === data) {
return i;
}
}
return -1;
}
二分查找
二分查找针对的是已经排好序的数据。过程很简单：就是每次取中间值，如果比中间值大，就取后边的那部分，再次循环；反之类似。
/**
* 二分法查找数组中数据
* @param {Array} ary 数组
* @param {Any} data 要查找数据
* @return {Number} 数据在数组中位置
*/
function binSearch(ary, data) {
var upperBound = ary.length - 1;
var lowerBound = 0;
var mid;
while (lowerBound <= upperBound) {
mid = Math.floor((lowerBound + upperBound) / 2);
if (ary[mid] < data) {
lowerBound = mid + 1;
} else if (ary[mid] > data) {
upperBound = mid - 1;
} else {
return mid;
}
}
return -1;
}
具体运行例子请看demo检索查找