二分搜索

[wl05]

二分搜索：

1. 选择数组的中间值。
2. 如果选中值是待搜索值，那么算法执行完毕(值找到了)。
3. 如果待搜索值比选中值要小，则返回步骤 1 并在选中值左边的子数组中寻找(较小)。
4. 如果待搜索值比选中值要大，则返回步骤 1 并在选中值右边的子数组中寻找(较大)。

代码实现如下：

function binarySearch(arr, value) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        const midIndex = Math.floor((low + high) / 2)
        const mid = arr[midIndex]
        if (mid < value) { // 说明在mid的左边
            low = midIndex + 1
        } else if (mid > value) { // 说明在mid的右边
            high = midIndex - 1
        } else if (mid === value) { // 找到了
            return midIndex
        }
    }
    return -1
}

const arr = [1, 2, 3, 4, 5, 6, 7]
console.log(binarySearch(arr, 7))