二分查找

微信公众号:Vegout 如有问题或建议,请公众号留言

二分查找

数据是海量的,从中提取有价值的信息是必要的,提取的过程也就是查找的过程。简单粗暴就是顺序查找,任何东西我一个一个来,不管你是有序无序,对我来说都一样。跟今天咱们所说的二分查找相比,顺序查找是低效的,二分查找可以更快的查找出结果。但同时,二分查找也是有开销的,如果说我们在一个数组中查找一个元素,那么二分查找要求这个数组是有序的。构建这个有序的数组就是相对于顺序查找多出来的开销。

假设我们有这么一个有序数组{0,1,2,3,4,5,6,7,8,9,10,16,35,67,77,778},如果想要查找16所在位置,二分查找的思想就是先将这个数组一分为二,找到中间元素,进行比较,如果大于中间元素,就去右子数组中继续这个过程,如果小于这个元素就去左子数组中继续这个过程,如果相等,那么就返回这个位置。这个数组有16个元素,下标是0到15,中间元素下标就是7,下标是7的元素也就是7,16大于7,于是我们再去下标8到15(右子数组)中重复查找过程,找到新的中间元素是坐标11,对应元素正好是16,于是返回11。

这个过程可以简单的用递归来实现,代码如下

    public static int search(int[] array,int key,int lo,int hi){
        if (lo>hi)return -1;
        int mid  = lo + (hi-lo)/2;
        if (key<array[mid])return search(array,key,lo,mid-1);
        else if(key>array[mid])return search(array,key,mid+1,hi);
        else return mid;
    }

也可以采取非递归的方式

public static int search(int[] array,int key,boolean notrecursion){
    int lo =0;
    int hi = array.length-1;
    while (lo<=hi){
        int mid  = lo +(hi-lo)/2;
        if (key<array[mid]) hi=mid-1;
        else if (key>array[mid])lo=mid+1;
        else return mid;
    }
    return -1;
}

这个代码实现的就是二分查找,其实我们对这个代码改动一点点就可以实现查找小于当前元素的元素个数这一功能。以上代码采取返回-1的方式告知用户未查找到此元素,我们把-1改为lo,这样就实现了查找小于当前元素的元素个数的功能。为什么呢?

对与递归这个示例代码来说,什么时候会进入if(lo>hi)这个分支?只有上次循环中lo等于了hi等于了mid,并且key不等与array[mid],于是亦或mid-1赋值给了hi,亦或mid+1赋值给了lo,反正使得lo大于了hi,此刻返回lo,lo大于hi,说明array[lo]定是大于我们所查找的Key,并且lo等于mid+1,于是lo也就是小于key的元素的数量值。lo正好等于小于所查找元素的个数。

代码中还有一个需要注意的地方,计算中间元素坐标用的是lo+(hi-lo)/2而不是(hi+lo)/2这是为什么呢?得出的结果是一样的,只不过前者避免了溢出的发生,我们使用的Int数据类型,他表示的数是有范围的,如果超出了这个范围发生了溢出,我们计算出的mid就可能不处在lo和hi之间,二分查找就会失效。

与顺序查找相比,二分查找确实是可以更快的查找出结果,但也正如前文所说,在构建这个有序数组上存在着一定的开销,也就是我们的插入动作有些缓慢,为了在保持高效二分查找的同时,也保证插入的高效性,也就需要一个新的数据结构,这个我们下文再谈。

本文分享自微信公众号 - Vegout(t10244201)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-03

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Unity游戏开发

基于反射、泛型的不定参数、不定类型的排序

方法相关 参数: string数组 - 全部要比较的字段名称 bool数组 - 每一个字段升序排序还是降序排序 IList<T>集合 - 要排序的Lis...

10530
来自专栏中科院渣渣博肆僧一枚

python中各种数据类型之间的转换

由于 json 语法规定 数组或对象之中的字符串必须使用双引号,不能使用单引号 (官网上有一段描述是 “A string is a sequence of ze...

48720
来自专栏中科院渣渣博肆僧一枚

Python字符串操作之字符串分割与组合

12.1 str.split():字符串分割函数 通过指定分隔符对字符串进行切片,并返回分割后的字符串列表。 语法:

13620
来自专栏前端说吧

HTML5 - websocket的应用 之 简易聊天室

HTTP协议中,服务器是基于“请求 到 响应”的一个模型的 。也就是说,服务器无法主动发送消息给客户端,他必须接收一个请求才能响应。

72620
来自专栏慕容千语的架构笔记

Java程序员进阶架构师的五个阶段,你到了哪各阶段?

之前有个讨论:实现同样功能,简洁代码一定比复杂代码效率高吗?有的说,还得看算法,如果算法相同,简洁代码效率应该会高一些。有的说,即使算法相同,简洁代码也不见得比...

14520
来自专栏Java架构师进阶

@Autowired的使用:推荐对构造函数进行注释

Spring Team recommends "Always use constructor based dependency injection in you...

16110
来自专栏happyJared

HashMap 和 Hashtable 的区别

15520
来自专栏中科院渣渣博肆僧一枚

tf.train.Saver

Saver类添加ops来在检查点之间保存和恢复变量,它还提供了运行这些操作的方便方法。检查点是私有格式的二进制文件,它将变量名映射到张量值。检查检查点内容的最佳...

33120
来自专栏Bingo的深度学习杂货店

【DP、双指针】5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume th...

11530
来自专栏大数据学习交流

大数据开发之常见九种数据分析方法

今天给大家分享一篇关于大数据开发常见的9种数据分析方法,首先数据分析是从数据中提取有价值信息的过程,过程中需要对数据进行各种处理和归类,只有掌握了正确的数据分类...

22130

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励