在线客服
扫描二维码
下载博学谷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))。
— 申请免费试学名额 —
在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!
相关推荐 更多
IT行业35岁后的职业规划建议
对于每一个IT人来说,35岁后是一个需要认真考虑职业发展前途的新阶段。到了这个阶段,大家也不必过于焦虑,虽然随着年纪的增长,30多岁的程序员在体力和工作效率上,可能会比不上年轻的新人,但是经验的积累对于IT人来讲,也是一笔宝贵的财富。本文就和大家一起来探讨下,IT行业35岁后的职业发展应该如何规划。
8967
2019-10-31 15:07:12
未来IT行业发展前景如何?
信息技术发展迅猛,现代生活的方方面面都已离不开计算机。时代下,对计算机人才的极大需求使得越来越多的人想要进入这一行业。IT行业的发展前景非常可观。IT行业的未来前景也吸引着更多的人学习IT。
4848
2020-05-22 11:22:53
小白入门编程需要了解哪些知识?
如今,IT行业凭借着高薪和广阔的发展前景成为无数人向往的职业之一,那么对于想要学习编程的小伙伴来讲,小白入门编程需要了解哪些知识呢?本文为大家整理了一些入门需要理解并掌握的基础知识,内容有计算机的定义、硬件的定义、软件的概念以及计算机基础知识。下面一起来看看吧~
3890
2020-06-22 15:35:14
学习编程的软件有哪些值得推荐?
工欲善其事必先利其器,学习光靠一味的死记硬背是不够的。尤其是学习IT编程,需要我们在练中学、学中练,才能真正掌握编程知识。因此了解并使用一些学习编程的软件是很有必要的,它们可以极大地提高我们的学习效率,帮助我们在学习编程的路上走得更远。本文将为大家盘点一下那些值得推荐的软件,分别是Eclipse、IDEA、Sublime Text、Notepad++、网易有道以及博学谷。
4901
2020-07-08 12:00:06
什么是网络编程?它是做什么的?
什么是网络编程?它是做什么的?简单解释一下,网络编程就是两台设备之间进行数据交换,最终到达通信的目的。要想深入的了解网络编程,我们必须弄清楚IP地址、端口号和网络协议这三者的概念,本文将会用最通俗易懂的例子,帮助大家理解网络编程的概念。
10429
2020-08-07 10:28:26