前言

二分查找是一个很基础的有序数组的查找算法。是要针对已经排好序的数据进行查找，它的时间复杂度是 O(log₂(n))。

原理

首先需要对查找的数组事先进行排序（默认从小到达排序）。

具体步骤如下：

1. 查找元素与数组中间元素与对比
2. 如果查找元素较小，则再取数组中间元素到最小元素之间的中间元素继续对比
3. 如果查找元素较大，则再取数组中间元素到最大元素之间的中间元素继续对比
4. 如果刚好相等，恭喜你，找到了
5. 2 和 3 的情况就继续查找下去，这样就可以找到了。

示意图 (来自 博客园)

代码实现

数组查找代码，查找出数组上的目标数字，有就返回该元素，没有就返回 undefined

/**
 * 二分查找
 */
function binarySearch (list, target) {
    if (!list.length) {
        return undefined
    }

    let len = list.length
    let mid = Math.floor(len / 2) // 中间元素索引
    let left = list.slice(0, mid) // 较小的入列
    let right = list.slice(mid + 1) // 较大的数列

    const midItem = list[mid]
    if (target === midItem) {
        return midItem
    }
    else if (target < midItem) {
        return binarySearch(left, target) // 递归，在较小数列中查找
    }
    else {
        return binarySearch(right, target) // 递归，在较大数列中查找
    }
}

我们实验一下

let sourceList = []
for (let i = 0; i < 100000001; i++) {
    sourceList.push(i*2)
}

const startTime = new Date().getTime()
let result = binarySearch(sourceList, 200000000)
console.log(new Date().getTime() - startTime) // 887
console.log(result) // 200000000

887毫秒的查找时间， 然后我们看顺序查找的时间:

/**
 * 顺序查找
 */
function search(list, target) {
    let len = list.length
    for (let i = 0; i < len; i++) {
        const item = list[i]
        if (item === target) {
            return item
        }
    }
    return undefined
}

let sourceList = []
for (let i = 0; i < 100000001; i++) {
    sourceList.push(i * 2)
}

const startTime = new Date().getTime()
let result = search(sourceList, 200000000)
console.log(new Date().getTime() - startTime) // 108
console.log(result) // 200000000

不会吧，108毫秒，难道我写错了？居然顺序查找快那么多？

其实并不是写错了，我发现是因为我进行了数组操作，例子中的数组长达 100000001，这样长度的数组进行slice操作要花费很多时间，所以得到的结果不理想，不过这并不方案我们理解这种查找方法。

上面的方法还有个问题，不能得到查找元素在数列中的位置，下面对这种方法进行优化：

/**
 * 二分查找
 * @param {*} list 
 * @param {*} target 
 * @returns 返回查找的目标在数组中的索引，未找到返回 -1
 */
function binarySearch(list, target, min, mid, max) {
    if (!mid) {
        // 参数初始化
        const len = list.length
        mid = Math.floor(len / 2)
        min = 0
        max = len // 注意，查找的数组中并不包含 max 为下标的元素
    }

    const midItem = list[mid]
    if (target === midItem) {
        return mid
    }
    if (target < midItem) {
        max = mid
    }
    else {
        min = mid + 1
    }
    mid = Math.floor((max - min) / 2) + min
    if (min === mid) {
        if (list[mid] === target) {
            return mid
        }
        return -1
    }
    return binarySearch(list, target, min, mid, max)
}

这是通过设置查找区间 min 肯 max，对数组进行分区二分查找，查找到返回索引，找不到返回 -1。 我们查找时间：

let sourceList = []
for (let i = 0; i < 100000001; i++) {
    sourceList.push(i*2)
}

const startTime = new Date().getTime()
let result = binarySearch(sourceList, 200000000)
console.log(new Date().getTime() - startTime) // 1
console.log(result) // 100000000
console.log(sourceList[result]) // 200000000

1 毫秒，好快。 因为没有对数组操作了，这个时间消耗很少很多好，针对一亿这个数字，最多只需要 log₂(n) 次查找，可以算出来最多只需要查找 26 次即可得出结果。而顺序查找平均也需要 5000 万次查找，这个效率一目了然了。

总结

二分查找真的高效率，学会他对于我们理解查找算法、以及对后面排序算法的学习也有帮助。