二分查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第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 条评论
登录 后参与评论

相关文章

来自专栏伪君子的梦呓

题解 ~ 输出三个数中的最大值 ~ C++ 做法

1365
来自专栏前端吧啦吧啦

数据结构(二)之算法基础

1104
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

3337
来自专栏云霄雨霁

有向图----有向环检测和拓扑排序

1451
来自专栏null的专栏

数据结构和算法——Huffman树和Huffman编码

Huffman树是一种特殊结构的二叉树,由Huffman树设计的二进制前缀编码,也称为Huffman编码在通信领域有着广泛的应用。在word2vec模型中,在构...

2666
来自专栏机器学习原理

我的机器学习numpy篇何为ndarray?ndarry创建生成正态分布ndarry属性修改形状ndarry运算ndarry切片矩阵转置聚合函数

前言: numpy是以矩阵为基础的数学计算模块,其基础为多维数组为ndarray 官方文档:(https://docs.scipy.org/doc/nump...

3608
来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

992
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

562
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(三)——向量

一、定义         这里不讨论向量严格的数学定义。在Madlib中,可以把向量简单理解为矩阵。矩阵是Madlib中数据的基本格式,当矩阵只有一维时,就是向...

21010
来自专栏娱乐心理测试

关于JS的浮点数计算精度问题解决方案

由于接触JS不久,关于JS的浮点数的计算更是之前没有用过,这次写JS项目发现的这个问题:0.1+0.2=0.3000000000004,为什么会出现这么奇怪的问...

1163

扫码关注云+社区