在线客服
扫描二维码
下载博学谷APP扫描二维码
关注博学谷微信公众号
二分法检索变种实现代码怎么写?二分法中每次排除都可以排除掉一半的情况,这样寻找效率很高。之所以叫二分,因为每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况。
二分法真的不简单,尤其是二分法的各个变种。最简单的二分法,就是从一个排好序的数组之查找一个key值。如下面的程序:
这个程序,相信只要是一个合格的程序员应该都会写。稍微注意一点, 每次移动left和right指针的时候,需要在mid的基础上+1或者-1, 防止出现死循环, 程序也就能够正确的运行。
但如果条件稍微变化一下, 你还会写吗?如,数组之中的数据可能可以重复,要求返回匹配的数据的最小(或最大)的下标;更近一步, 需要找出数组中第一个大于key的元素(也就是最小的大于key的元素的)下标,等等。这些,虽然只有一点点的变化,实现的时候确实要更加的细心。下面列出了这些二分检索变种的实现。
1、找出第一个与key相等的元素
2、找出最后一个与key相等的元素
3、查找第一个等于或者大于Key的元素
4、查找第一个大于key的元素
5、查找最后一个等于或者小于key的元素
6、查找最后一个小于key的元素
总结:
算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。
基本思想:假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
如果当前位置arr[k]值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low,mid-1];
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid+1,high],
直到找到为止,时间复杂度:O(log(n))。
— 申请免费试学名额 —
在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!
相关推荐 更多
计算机语言入门方法有哪些?
计算机语言入门方法有哪些?入门编程语言很简单,精通掌握一门编程语言需要一个艰苦的过程。想要学学好计算机语言需要有好的学习方法。使用一些计算机语言工具总结学习过程中的技巧,通过不断积累知识才能融汇贯通。
6424
2019-08-14 16:04:54
Activity生命周期的知识点详解
在掌握Android应用开发的学习过程中,Activity生命周期相关知识点是必须掌握的基础内容。本文将会为大家详解Activity生命周期的有关知识,带大家了解什么是Activity生命周期,生命周期的流程以及四个状态,最终达到帮助大家完整掌握Activity用法的目的。下面就让我们一起来学习一下Activity的生命周期吧!
4490
2020-02-04 15:39:14
HTTP面试题汇总附答案
HTTP相信大家都不陌生了,作为一种应用最为广泛的网络传输协议,它也常常出现在面试考题之中。本文汇总了目前比较常考的HTTP面试题,并整理好了所有HTTP面试题的答案,希望可以帮助到正在复习HTTP相关知识点的小伙伴~
5551
2020-05-07 17:29:13
少儿编程有必要学吗?
随着社会的不断进步,人们的消费水平和生活水平都不断提高,越来越多的家长愿意花费更多的金钱和精力投入到对孩子的培养中。而在各种少儿培训中,除了舞蹈、美术、音乐等传统兴趣培训意之外,“少儿编程”也被人们更多关注。儿童编程在把计算机编程融合孩子兴趣的同时,加强孩子思维能力的锻炼,学习编程语言,可以锻炼孩子的逻辑思维
5931
2020-05-22 14:42:07
安卓编程入门学习要具备哪些能力?
随着安卓的不断发展壮大,安坐产品所占的市场份额也在不断扩张,全球安卓设备的使用量也不断提升,这也就导致安卓编程人才的需求量与日俱增,可以看出安卓编程的发展前景十分广阔。所以就有了许多人想要想要去学习安卓编程技术,那么安卓编程入门要具备那些能力,学什么?
3570
2020-06-16 15:53:06