JS实现二分搜索

二分查找的前提为：数组、有序。逻辑为：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。

非递归实现

function binarySearch(arr, target){
    var h = arr.length - 1,
        l = 0;
    while(l <= h){
        var m = Math.floor((h + l) / 2);
        if(arr[m] == target){
            return m;
        }
        if(target > arr[m]){
            l = m + 1;
        }else{
            h = m - 1;
        }
    }
  
    return false;
}
var arr = [-34, 1, 3, 4, 5, 8, 34, 45, 65, 87];
binarySearch(arr,4);

递归版本

function binarySearch (arr, target, start, end) {
    if (end == undefined) { // 此处不能写成end = end || arr.length - 1形式，
    // 因为递归调用的时候参数的域变了。如果不用这种写法，可以将此处if语句去掉，直接在外面调用函数时传参。
        end = arr.length - 1
    }
    if (start == undefined) {
        start = 0
    }
    var m = Math.floor((start + end) / 2)
    if (arr[m] == target) {
        return m
    }
    if (start >= end) {
        return false
    }
    if (target < arr[m]) {
        return binarySearch(arr, target, start, m - 1)
    } else {
        return binarySearch(arr, target, m + 1, end)
    }
}
var arr = [-34, 1, 3, 4, 5, 8, 34, 45, 65, 87]
binarySearch(arr, 4)