二分法查找

场景

💡假设有这样一个“猜数字”的游戏：裁判在1~100之间想一个数字，我们报数字来猜裁判心中所想的数字，裁判能提示我们所猜的这个数字是“大了”，“小了”，或者“猜对啦！”，直到裁判说“猜对啦”，这个游戏才算结束！

方案一

最直接的一个办法就是，我们可以有序的从1报到100，代码实现如下：

// 用随机数来模拟裁判心中所想的数字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的数字是${num}`)
// for循环模拟我们猜的过程
for(let i = 1; i <= 100; i++) {
    if(i < num){
        console.log('小了')
    } else if(i === num){
        console.log(`猜中啦！这个数字是${i}`)
        console.log(`一共猜了${i}次`)
        break
    }
}

猜想

以上确实是不失为一种方案，但可以看出，这种方案最少需要猜测1次，最多需要猜测100次。想一想，有没有一种方法，能够让我们尽可能少的猜测就能猜到这个数字。假如我们从中间开始猜，每次都能排除掉一半的数字，然后继续在剩下的数字中取中间值，这样又能排除掉一半......重复这个动作，直到找到正确的数字，这便是二分查找算法了。并且我们还有一个“大了”的条件我们还没有用上，如果用这种方式，那么这个条件就能用上了。

方案二

每次我们从最中间的数开始猜，如果有小数点（1~100最中间的数是50.5）就进行向下取整。

// 还是用随机数来模拟裁判心中所想的数字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的数字是${num}`)
// 定义（0~100）这个区间的小值lit，最大值big，和中间值mid，i用来记录循环的次数
let lit = 0, big = 100, mid = Math.floor((lit + big) / 2), i = 0
// 只要范围没有缩小到只剩一个元素，就循环
while(lit <= big) {
    i++ 
    mid = Math.floor((lit + big) / 2)
    // 如果中间值比num小，则把mid+1赋给lit
    if(mid < num) {
        console.log('小了')
        lit = mid + 1
    } else if(mid > num) { // 如果中间值比num大，则把mid-1赋给big
        console.log('大了')
        big = mid - 1
    } else { // 如果相等，则打印mid和循环次数，并跳出循环
        console.log(`猜对啦！这个数字是${mid}`)
        console.log(`一共猜了${i}次`)
        break
    }
}

结论

方案一，最多需要猜测100次，而方案二最多只需要7次，可见二分查找的效率比普通循环的要高很多。一般对于包含了n个元素的有序列表来说，二分查找最多只需要 ${log_2{n}}$ 次就能找到。

最后编辑于：2020.08.20 10:04:23