二分搜索

递归实现

// 递归对区间[l, r]的元素使用二分查找算法
function __binarySearch(arr, l, r, e){
    // 1. 递归终止的条件
    if (l > r) {
        return;
    }

    // 2. 开始对左右区间进行递归搜索
    var middle = Math.floor(l + (r - l) / 2);
    console.log('finding ……', middle, e, arr[middle]);
    if (e < arr[middle]) {
        // 使用递归的方法进行二分查找的时候，需要将每次递归的时候的结果返回给下一个循环调用
        return __binarySearch(arr, l, middle - 1, e);

    } else if (e > arr[middle]) {
        return __binarySearch(arr, middle + 1, r, e);
    } else {
        return middle;
    }

    // 找不到的情况的处理
    return -1;
}


function binarySearch(arr, e){
    // 实现二分查找算法(arr[0, arr.length - 1])
    return __binarySearch(arr, 0, arr.length - 1, e);
}

var arr = [1, 2, 3, 4, 5];
var res = binarySearch(arr, 5);
console.log('find ok : ', res);

非递归实现

function binary_search(arr, key) {
    var low = 0,
        high = arr.length - 1;
    while(low <= high){
        var mid = parseInt((high + low) / 2);
        if(key == arr[mid]) {
            return  mid;
        } else if(key > arr[mid]) {
            low = mid + 1;
        } else if(key < arr[mid]) {
            high = mid -1;
        } else{
            return -1;
        }
    }
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr, 10);
console.log(result); // 9