美文网首页
二分法查找

二分法查找

作者: 苏夏噢 | 来源:发表于2020-08-19 19:16 被阅读0次

场景

💡假设有这样一个“猜数字”的游戏:裁判在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}}次就能找到。

相关文章

  • 二分法查找

    二分法基本查找 二分法遍历查找

  • 二分法查找

    二分法查找的前提是数组必须排序!!!二分法查找的前提是数组必须排序!!!二分法查找的前提是数组必须排序!!!二分法...

  • 刷前端面经笔记(九)

    1.JavaScript实现二分法查找? 二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找...

  • 数据结构-递归

    二分法查找

  • 查找算法

    三种查找算法:顺序查找,二分法查找(折半查找),分块查找,散列表

  • 二分查找

    以二分法来提升查找效率 二分法查找到key的合适位置 put get delete 二分查找的查找操作为O(log...

  • 算法和排序

    1、线性查找 2、二分法查找 3、冒泡排序

  • 查找算法

    查找算法 顺序查找法 时间复杂度:O(n) 二分法查找 二分法查找适用于有顺序的序列 时间复杂度:O(n) 核心思...

  • 算法图解1-2/11

    原书作者 Aditya Bhargava 1 算法简介 1.1 二分法查找 二分法查找,正是猜数字游戏的玩法:A...

  • 前端面试之算法二分法

    使用二分法的前提是,目标数组的元素必须是有序排列的,所以二分法属于有序查找算法 二分法又称为“折半查找”,从数组的...

网友评论

      本文标题:二分法查找

      本文链接:https://www.haomeiwen.com/subject/dygrjktx.html