二分查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第5篇《二分查找》,非常赞!希望对大家有帮助,大家会喜欢!

前面系列文章:

归并排序

#算法基础#选择和插入排序

由快速排序到分治思想

算法基础:优先队列

二分查找,就和他的名字一样,把一个数组找到他的中间的值和我想要找的值,进行对比,这个时候可以分为三种情况 1、比中间值大,我就到中间值到最大值的范围内去找。

2、比中间值小,那就去最小值和中间值之间去寻找。 如果正好相等那恭喜你找到了。然后照这个思路不断的递归迭代就可以确定是否有对应的值了。

 publicint rank(Key key ){
 intl1= keys.length;
 intl0=0;
 while(l0<l1){
 intmid=l0+(l1+l0)/2;
 intb = key.compareTo(keys[mid]);
 if(b<0)  l0=mid+1;  //+1和下面-1 的作用是为了找不到是跳出
 elseif(b>0)  l1=mid-1;
 elsereturnmid;
              }
 returnl0;
       }

特性: 查找速度 lgN 插入速度在N-2N之间

优缺点:

相对于普通顺序查找速度由二次方到对数级块了很多。

缺陷:数组必须有序的

应用:

用二分查找法找寻边界值

之前的都是在数组中找到一个数要与目标相等,如果不存在则返回-1。我们也可以用二分查找法找寻边界值,也就是说在有序数组中找到“正好大于(小于)目标数”的那个数。

用数学的表述方式就是:

在集合中找到一个大于(小于)目标数t的数x,使得集合中的任意数要么大于(小于)等于x,要么小于(大于)等于t。

用二分查找法找寻区域

之前我们使用二分查找法时,都是基于数组中的元素各不相同。假如存在重复数据,而数组依然有序,那么我们还是可以用二分查找法判别目标数是否存在。不过,返回的index就只能是随机的重复数据中的某一个。

此时,我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏项勇

[Android笔记7]之通过DatePickerDialog,TimePickerDialog调用系统时间设置

2753
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9744
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2272
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2631
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7475
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5896

扫码关注云+社区