编辑代码

// 二分查找
// 前提：数组、有序
// 原理：优先和数组中间元素比较，如果等于中间元素直接返回，否则取半继续查找
// 1. 二分查找-递归
function binarySearch1 (arr, target, start = 0, end = arr.length - 1) {
    var m = Math.floor((start + end) / 2);
    if (arr[m] == target) {
        return m;
    }
    if (start >= end) {
        return -1;
    }
    if (target < arr[m]) {
        return binarySearch1(arr, target, start, m - 1);
    } else {
        return binarySearch1(arr, target, m + 1, end);
    }
}
// 2. 二分查找-非递归
function binarySearch2 (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 -1;
}

var arr = [-34, 1, 3, 4, 5, 8, 34, 45, 65, 87];
console.log(binarySearch1(arr, 4));
console.log(binarySearch2(arr, 4));