• 在线客服

  • 扫描二维码
    下载博学谷APP

  • 扫描二维码
    关注博学谷微信公众号

  • 意见反馈

原创 二分法检索变种实现代码怎么写?

发布时间:2020-08-26 15:51:03 浏览 3492 来源:博学谷 作者:吾非鱼

      二分法检索变种实现代码怎么写?二分法中每次排除都可以排除掉一半的情况,这样寻找效率很高。之所以叫二分,因为每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况。


      二分法真的不简单,尤其是二分法的各个变种。最简单的二分法,就是从一个排好序的数组之查找一个key值。如下面的程序:

     

    从一个排好序的数组之查找一个key值
      这个程序,相信只要是一个合格的程序员应该都会写。稍微注意一点, 每次移动left和right指针的时候,需要在mid的基础上+1或者-1, 防止出现死循环, 程序也就能够正确的运行。


      但如果条件稍微变化一下, 你还会写吗?如,数组之中的数据可能可以重复,要求返回匹配的数据的最小(或最大)的下标;更近一步, 需要找出数组中第一个大于key的元素(也就是最小的大于key的元素的)下标,等等。这些,虽然只有一点点的变化,实现的时候确实要更加的细心。下面列出了这些二分检索变种的实现。


      1、找出第一个与key相等的元素

     

    找出第一个与key相等的元素
      2、找出最后一个与key相等的元素

     

    找出最后一个与key相等的元素
      3、查找第一个等于或者大于Key的元素

     

    查找第一个等于或者大于Key的元素
      4、查找第一个大于key的元素

     

    查找第一个大于key的元素

     

      5、查找最后一个等于或者小于key的元素

     

    查找最后一个等于或者小于key的元素
      6、查找最后一个小于key的元素

     

    查找最后一个小于key的元素 

          总结:
      算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。
      基本思想:假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
      如果当前位置arr[k]值等于key,则查找成功;
      若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low,mid-1];
      若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid+1,high],
      直到找到为止,时间复杂度:O(log(n))。

    申请免费试学名额    

在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!

上一篇: 博学谷学员参加新网银行金融科技挑战赛获优胜奖 下一篇: 程序员常用的API接口管理工具有哪些?

相关推荐 更多

热门文章

  • 前端是什么
  • 前端开发的工作职责
  • 前端开发需要会什么?先掌握这三大核心关键技术
  • 前端开发的工作方向有哪些?
  • 简历加分-4步写出HR想要的简历
  • 程序员如何突击面试?两大招带你拿下面试官
  • 程序员面试技巧
  • 架构师的厉害之处竟然是这……
  • 架构师书籍推荐
  • 懂了这些,才能成为架构师
  • 查看更多

扫描二维码,了解更多信息

博学谷二维码