前端算法之查找算法

• 顺序查找

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 23, 45, 55, 44, 22, 33];
function find(array, data) {
    var length = array.length;
    for (var i = 0; i < length; i++) {
        if (data === array[i]) {
            return i;
        }
    }
    if (i === length) {
        return -1;
    }
}
console.log(find(arr, 2));   //1 
console.log(find(arr, 33));  //14
console.log(find(arr, 100)); //-1

• 二分法查找:适用于有序的数据

var arr = [];
for (var m = 1; m <= 5; m++) {
    arr.push(m);
}
console.log(arr);  //1,2,3,4,5

function binarySearch(array, data) {
    var l = array.length;
    var low = 0,
        high = l - 1;
    while (low <= high) {
        var middle = Math.floor((low + high) / 2);
        if (data < array[middle]) {
            high = middle - 1;
        } else if (data > array[middle]) {
            low = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}
console.log(binarySearch(arr, 50));     //49
console.log(binarySearch(arr, 33));     //32
console.log(binarySearch(arr, 1));      //0
console.log(binarySearch(arr, 100));    //99
console.log(binarySearch(arr, 1000));   //-1