二分查找

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

相关文章

来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

962
来自专栏java一日一条

前端面试中常见的算法问题总结

虽说我们很多时候前端很少有机会接触到算法。大多都交互性的操作,然而从各大公司面试来看,算法依旧是考察的一方面。实际上学习数据结构与算法对于工程师去理解和分析问题...

1061
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3335
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

2467
来自专栏赵俊的Java专栏

寻找旋转排序数组中的最小值

1555
来自专栏阮一峰的网络日志

快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 ? 排序算法(Sorting al...

2815
来自专栏chenjx85的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1152
来自专栏趣谈编程

快速排序(基础版)

1503
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

42110
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

2867

扫码关注云+社区