前端算法之二分查找

举报
赵小左 发表于 2022/11/09 16:08:01 2022/11/09
【摘要】 ​二分查找又称之二分折半查找法,指的是在一个有序(升序,或者降序)的列表中进行查找某一个值的办法。它的意思是,二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。如果查以空的一半结束,则无法满足条件,并且无法找到目标。在实际情况中也可以这么理解。1. 有一个有序...

二分查找又称之二分折半查找法,指的是在一个有序(升序,或者降序)的列表中进行查找某一个值的办法。它的意思是,二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。如果查以空的一半结束,则无法满足条件,并且无法找到目标。

在实际情况中也可以这么理解。

1. 有一个有序的列表(例如某个升序或者降序的大批量数据)

如:[1,2,3,4,5,6,7,8,9,...,1556346346]. 这么个列表,需要你去从中间找出一个值,

老方法:

假如这个值就是 1556346346。按照暴力解题法,我们会去一个个的循环这个列表。一直循环到第 1556346346 位就结束。发现有相等的。我们结束这个循环。也就是说暴力解题会让我们循环这个数组 至少 1556346346次才能拿到 对应的 1556346346。

二分查找:

那么二分查找如何进行的呢?

它每次是取当前有序列表的一半,也就是上取上述列表的中间下标。然后用中间下标的值来判断是否与我们所要取的值,如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。


现实中举个例子来说:

老师在台上拿了一本算法书在讲算法。一边讲一边说:“同学们,我手里这本书是一个有序列表,一共有100页。那么我如何在最短时间找到第10页呢?”

1. 首先,我们找到书100页的一半,也就是50页。我们用50页来判断10页。发现50页大于10页。所以我们要找的10页存在于我们将这本书折半后的前50页中。这时候我们就可以将这本书的后50页撕掉。只剩下前50页。

2. 我们再剩下的前50页中再取它的中间值,25与10页判断,发现25还是大于10.所以依旧还是在这50页的前一半。所以我们依旧将书本剩下的50页以25页为中间,撕掉后25页。现在总书就剩下了25页。

3. 我们再去25 的中间值。等于12.5. 那么12.5 在我们这里没法计算,所以我们需要给它取整。所以我们25的中间值,我们在这里取 12.。然后用12 再去和10 判断 发现依旧大于10 .所以我们继续将25页 的 后面13页撕掉(书本剩下总25页,取中间整数我们为12页。所以后半部分剩下13页。)。这时候整本书就剩下了12页。

4. 我们继续取剩下12页的中间值,6.用来与10判断。这时候发现 它小于我们要取的页面值了。这时候怎么办,我们需要将12页的前6页撕掉。因为这个中间值已经小于我们要判断的值,所以这个值一定是在12页中间值6的后面。所以我们撕掉12页的前6页。这时候整书剩下6,分别为【7,8,9,10,11,12】页。

5. 依旧我们继续判断。取剩下6页的折中第三位,也就是第九页。我们继续判断,发现九依旧小于10。所以我们同样道理,将9页之前的全部撕掉。这时候整本书就剩下了 10,11,12页。

6. 同上依旧折中取中间值并取整获取到的值为1. 也就是说第10页。 我们这时候去判断 发现 10页 等于 10.我们的判断成立。二分查找结束。


而用代码表示出来就如下:

  var search = function (nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = (left + right) >> 1
            if(nums[mid] === target){
                return mid
            }else if (nums[mid] > target) {
                right = mid -1 
            }else {
                left  = mid + 1
            }
        }
        return -1;
    };
    console.log(search([1,2,3,4,5,6,7,...,100], 10))

上述代码的意思是,初始我们取一个最左侧与列表最右侧的值。

然后我们判断,当前左侧是否小于等于右侧。(此处的意思就是,当小于的时候,我们就证明它们之间还有值,我们依旧需要判断)。

第三步则是取 左右两个值的中间值。

第四步判断中间值是否等于我们索要得值。

如果不是,那就判断是否大于我们想要的值或者小于想要的值。

如果大于我们的值。

那就证明我们想要的值在列表折半后的左侧。那么我们就将最右侧的值移动到中间值的左侧来。

如果小于,则证明我们要的值在列表折半后的右侧,我们就需要将最左侧的值移动到中间值的右侧取。

然后再进行折中判断。直到相等为止。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。