JavaScript 检索算法

[Checkson]

前言

作为最基本的计算机编程任务，数据检索已经被研究了很多年，在这里，我们只讨论如何查找特定的值。

在列表中查找数据有两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；二分查找适用于元素已排序的列表。二分查找效率更高，但是你必须在进行查找之前花费额外的时间将列表中的元素排序。

顺序查找

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

普通查找

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

查找最小值

function findMin (arr) {
    var min = arr[0];
    for (var i = 1, len = arr.length; i < len; i++) {
        if (arr[i] < min) {
              min = arr[i];
        } 
    }
    return min; 
}

查找最大值

function findMax (arr) {
    var max = arr[0];
    for (var i = 1, len  = arr.length; i < len; i++) {
        if (arr[i] > max) {
              max = arr[i];
        }
    }
    return max;
}

二分查找

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

function binSearch (arr, data) {
    var len = arr.length
    var high = len - 1;
    var low = 0;
    while (low <= high) {
        var mid = Math.floor((low + high) / 2);
        if (arr[mid] < data) {
             low = mid + 1;
        } else if (arr[mid] > data) {
             high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

因为这一章相对比较简单，我们过一遍就差不多了。