二分查找

思路：

1. 初始化
   • left = 0
   • right = arr.length -1
2. while 循环
   • 终止条件 left <= right
   • 获取中间下标 mid
   • 目标值 比较 中间值 arr[mid]
     • 等于返回 下标
     • 小于中间值 right = mid -1
     • 大于中间值 left = mid +1
3. 未找到返回 -1

/**
 * @description     二分查找递归实现，若传入的数组无序，则采用上面的排序方法，进行排序
 * @param {*} target 查找的值
 * @param {Array} arr 需传入有序数组，
 * @param {Number} left 开始查找的位置
 * @param {Number} right 结束查找位置
 */
function binarySearch(target, arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (target === arr[mid]) {
            return mid;
        } else if (target < arr[mid]) {
            right = mid -1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

let binaryArray = [ 0, 1, 1, 2, 2, 4, 21, 34, 56 ];
console.log(binarySearch(21,binaryArray))