在线客服
扫描二维码
下载博学谷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编程怎么样?
女生做什么工作比较好?很多人说女生学习教师、护士、会计等比较好,说实话女生在职场中要比男生处境艰难,很多核心岗位或部门内部晋升很多领导会考虑男性多一些。这不是普遍现象,目前在职场中女性地位也越来越高。女生做什么工作比较好并不能一概而论。女生学IT编程怎么样?
8468
2019-08-07 16:52:24
编程入门先学什么语言?
编程入门先选一门简单的语言进行学习,对编程有一个初步的认识,建议选择C、Java、Python,这些都是不错的入门语言重要的是掌握编程思想、找到编程感觉,而不是死记硬背语言本身,很多语言是一致的。
14133
2019-11-27 14:38:57
IT编程培训一年多少钱?
IT编程培训一年多少钱?首先IT编程培训的科目有很多,目前比较主流热门的科目一般有Java、Python、前端、大数据、运维、软件测试等等。考察市面上的多家IT培训机构,我们大概可以发现线下的培训费用一般都在15K~25K,根据学习科目的不同,价格也会有一些差异。不过除了学费,还有许多朋友是离开家乡来参加培训的,因此还要加上住宿和生活费,因此IT编程培训一年的花费会更大。
11076
2020-04-10 15:27:07
互联网研发岗位面试指南
因为疫情的影响,今年比往年的面试环境更加残酷。互联网研发岗位一向是各大企业公司需求的核心岗位,因此从这个角度来讲,研发岗位的求职者仍旧有着许多的机会。那么,大家应该如何准备面试把握好机会呢?本文将从考核重点、专业准备、项目介绍和远程面试注意事项几个重点,为大家呈现上一份详细的互联网研发岗位面试指南。
4371
2020-04-13 15:13:28
新手学编程有哪些要求?准备什么?
想学编程需要具备数学的基本常识,熟悉常用的英语词汇,有一定的计算机基础。编程是创造新事物的工作需要从业者具备创造事物的能力,学好编程的捷径就是不断敲代码练习,将理论知识运用到实际的项目中学以致用。
4465
2021-04-07 14:47:16