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

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

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

　　二分法真的不简单，尤其是二分法的各个变种。最简单的二分法，就是从一个排好序的数组之查找一个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))。

IT编程入门学习

— 申请免费试学名额 —

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

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

相关推荐 更多

2019年IT软件开发中Python、Java、Go语言哪个前景好？

2019年IT软件开发中Python、Java、Go语言各有各的优势，24岁的Java，早已不再年轻，但依然是最流行的编程语言；为软件开发而生的Go语言，可以在不损失应用程序性能的情况下降低代码的复杂性；Python更是力压C++，占据最受欢迎排行榜的Top3成为开发者最想要掌握的技能之一。

10653

2019-07-15 15:44:12

IT编程编程语言就业前景
网络菜鸟如何自学编程？有什么学习编程的办法吗？

当你身为一个菜鸟级别，开始打算自学编程时，你要面临思想的转变，网络菜鸟如何自学编程？有什么学习编程的办法？是你开始思考的第一步，接下来的二三步让我跟你说一说关键点。

4193

2020-01-09 09:43:58

IT编程编程语言
编程小白应该怎样开始学习编程？

对于编程小白来讲，入门学习编程常常会遇到各种各样的困扰，比如担心自己没有基础而导致学不会，学习的内容太多而迷失方向，收集了不少学习资源但是学起来很吃力等等。其实这些困扰都可以总结成一个问题，即编程小白应该怎样开始学习编程？其实要解决这个问题也不难，下面我们一起来看看零基础小白学习编程的具体路线吧！

4881

2020-02-03 18:36:23

IT编程 IT培训机构
程序员这个岗位可以干多少年？

程序员作为当前高薪且极具发展前途的热门岗位，吸引了许多人的青睐。然而也有一些人担心程序员只是一个吃青春饭的岗位，到了30岁以后就会失去竞争力。实际上，这完全是大众对于这个行业存在普遍误解。虽然，一个程序员的编程能力和编程年纪不一定成正比，但是在绝大多数的情况下，参与更多项目开发经验的资深程序员一定比年轻的程序员更吃香。下面我们来详细看看程序员这个岗位可以干多少年。

4888

2020-02-28 13:43:05

IT编程程序员发展前景
安卓编程该如何入门？

对于初学安卓编程的小白来说，掌握基础才是重中之重。许多新手都喜欢从网上找找资料，以及观看各大媒体平台的学习资源，资源是最不缺的东西。那么该如何找到合适自己的学习方法才是最重要的，对于安卓编程该如何入门。

3481

2020-05-26 10:28:55

编程语言入门学习