热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

二分查找(BinarySearch)常见问题解决方法总结

缘由今天浏览何登成的技术博客无意中发现了写的blog,二分查找(BinarySearch)需要注意的问题,以及在数据库内核中的实现。随想总结下二分查找的

缘由

今天浏览 何登成的技术博客  无意中发现了写的blog,二分查找(Binary Search)需要注意的问题,以及在数据库内核中的实现。

随想总结下二分查找的常见问题。

问题背景

今年的实习生招聘考试,我出了一道二分查找(Binary Search)的题目。题目大意如下:

给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7]。

问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现。

注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定。

 在这片博客中作者也详细说明了,二分查找的重要性,比如在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的

SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位。 可以看到二分查找在现实的重要性。

二分查找算法的思想

二分查找法主要是解决在“一堆数中找出指定的数”这类问题。

而想要应用二分查找法,这“一堆数”必须有一下特征:

  • 存储在数组中
  • 有序排列

所以如果是用
链表
存储的,就无法在其上应用
二分查找法
了。

其实二分查找算法的思想很简单,在《编程珠玑》一书中的描述:

 在一个包含x的数组内,二分查找通过对范围的跟综来解决问题。开始时,范围就是整个数组。通过将范围中间的元素

与x比较并丢弃一半范围,范围就被缩小。这个过程一直持续,直到在x被发现,或者那个能够包含t的范围已成为空。

 Donald Knuth在他的《Sorting and Searching》一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个

没有bug的二分查找算法却是在12年后才被发表出来。

注意中间值下标的计算,如果写成(low+high)/2,low+high可能会溢出,从而导致数组访问出错。改进的方法是将计算方式

写成如下形式:low+ ( (high-low) >>1)。

常见问题解决

在何登成的技术博客中的问题四 “如何查找第一个/最后一个等值”,这个大牛只是简单的说明了下,并没有详细说明怎么解决

这个问题,下面来探讨 怎么解决 当所给有序重复数组 中查找 某个值出现的 第一个 和最后一个位置。

主要是下面三个问题:

1)二分查找元素x的下标,如无 return  -1

2)二分查找返回x(可能有重复)第一次出现的下标,如无return  -1

3)二分查找返回x(可能有重复)最后一次出现的下标,如无return  -1

对于问题1 我们只需要 利用最原始的的二分查找即可。

代码如下:

[cpp] view plaincopy
  1. /*  
  2. bin_search 二分查找元素x的下标,如无 return -1 
  3. low,high 分别为待查元素的区间的 上下界(包含边界). 
  4. x为待查元素. 
  5. 注意 low <&#61; high  
  6. */  
  7. int bin_search(int *a, int low, int high, int x)  
  8. {  
  9.     if(NULL &#61;&#61; a || low > high)  
  10.         return -1;  
  11.   
  12.     int mid;  
  13.     while(low<&#61;high)//注意是<&#61;&#xff0c;若是<会找不到边界值情况  
  14.     {  
  15.         mid &#61; low &#43; ((high-low)>>1);  
  16.         if(x
  17.             high &#61; mid-1;  
  18.         else if(x>a[mid])  
  19.             low &#61; mid &#43;1;  
  20.         else  
  21.             return mid;  
  22.     }  
  23.     return -1;  
  24. }  




对于问题2&#xff0c;二分查找返回x(可能有重复
)第一次出现的下标
&#xff0c;如无return  -1。

我们只需找到x重复出现情况下的第一次出现的下标。则我们只需用a[mid]和元素x进行比较&#xff0c;当a[mid]

此时待查元素肯定在待查区间的右半部分 显然此时 不包括 mid 所以有 low &#61; mid&#43;1, 若a[mid]>&#61;x时, 因为我

们查找的是x第一次出现的位置,我们不关心x最后出现的位置,所以此时high下标为mid,直到 low &#61;&#61; high 终止

循环&#xff0c;并且比较a[low]是否为x,若是则 找到。

总的思路是&#xff1a;

把有序序列分成2个序列:[first,mid][mid&#43;1,last) 当 a[mid]

当 a[mid]>&#61;x 时 使用序列[first,mid]。

还是看代码吧。

[cpp] view plaincopy
  1. /*  
  2. binS_first二分查找返回x(可能有重复)第一次出现的下标&#xff0c;如无return -1 
  3. low,high 分别为待查元素的区间的 上下界(包含边界). 
  4. //分成2个序列:[first,mid][mid&#43;1,last) 
  5.   x为待查元素.注意 循环结束条件&#xff0c;low &#61;&#61; high */  
  6. int binS_first(int *a, int low, int high, int x)  
  7. {  
  8.     if(NULL &#61;&#61; a || low > high)return -1;  
  9.     int mid;  
  10.     while(low
  11.     {  
  12.         mid&#61;low&#43;((high-low)>>1);//计算中点  
  13.         if(a[mid]//   
  14.             low&#61;mid&#43;1;  
  15.         else // >&#61;x  
  16.             high&#61;mid;  
  17.     }  
  18.     if(a[low] &#61;&#61; x)  
  19.         return low;  
  20.     return -1;  
  21. }  




 


对于问题3&#xff0c;二分查找返回x(可能有重复)最后一次出现的下标&#xff0c;如无return  -1

其实和问题2的思路差不多。

只是在 while中我们假定 low&#43;1

接下来的while 情况和问题2等价。我们现在关心的是 x(可能有重复)最后一次出现的下标&#xff0c;所以现在我们不关心他

第一次出现下标的位置, 当 a[mid]<&#61;x 时 low &#61; mid, 否则 a[mid] >x 此时 high &#61; mid -1. 代码如下&#xff1a;

[cpp] view plaincopy
  1. /*  
  2. binS_last二分查找返回x(可能有重复)最后一次出现的下标,如无return -1 
  3. low,high 分别为待查元素的区间的 上下界(包含边界). 
  4. x为待查元素. 
  5. 注意 循环结束条件&#xff0c;low&#43;1 &#61;&#61; high  
  6. */  
  7. int binS_last(int *a, int low, int high, int x)    
  8. {    
  9.     if(NULL &#61;&#61; a || low > high)  
  10.         return -1;  
  11.     int mid;      
  12.     while(low&#43;1//**     
  13.     {    
  14.         mid&#61;low&#43;((high-low)>>1);    
  15.         if(a[mid]<&#61;x)  // <&#61;x  
  16.             low &#61; mid;    
  17.         else  // >x  
  18.             high&#61;mid-1;    
  19.     }    
  20.     if(a[high] &#61;&#61; x)//先判断high  
  21.         return high;  
  22.     else if(a[low] &#61;&#61; x)  
  23.         return low;  
  24.     return -1;  
  25. }    

查找重复元素出现的第一次 最后一次位置总结如下&#xff1a;

二分查找返回x(可能有重复)第一次(最后一次)出现的下标找最小的等号放>&#61;x位置(high),找最大的等号放<&#61;x的位置(low)。
其中a[mid]在和待查找元素x比较中带 &#61; 的&#xff0c;在对low 或者high赋值时一定为 mid&#xff0c;其它情况(<或>)则为mid&#43;(-)1.

总的测试程序。

[cpp] view plaincopy
  1. #include   
  2. /* 
  3. bin_search 二分查找元素x的下标&#xff0c;如无 return -1 
  4. low,high 分别为待查元素的区间的 上下界(包含边界). 
  5. x为待查元素. 
  6. 注意 low <&#61; high 
  7. */  
  8. int bin_search(int *a, int low, int high, int x)  
  9. {  
  10.     if(NULL &#61;&#61; a || low > high)  
  11.         return -1;  
  12.   
  13.     int mid;  
  14.     while(low<&#61;high)//注意是<&#61;&#xff0c;若是<会找不到边界值情况  
  15.     {  
  16.         mid &#61; low &#43; ((high-low)>>1);  
  17.         if(x
  18.             high &#61; mid-1;  
  19.         else if(x>a[mid])  
  20.             low &#61; mid &#43;1;  
  21.         else  
  22.             return mid;  
  23.     }  
  24.     return -1;  
  25. }  
  26. /* 
  27. binS_first二分查找返回x(可能有重复)第一次出现的下标,如无return -1 
  28. low,high 分别为待查元素的区间的 上下界(包含边界). 
  29. //分成2个序列:[first,mid][mid&#43;1,last) 
  30. x为待查元素. 
  31. 注意 循环结束条件&#xff0c;low &#61;&#61; high */  
  32. int binS_first(int *a, int low, int high, int x)  
  33. {  
  34.     if(NULL &#61;&#61; a || low > high)return -1;  
  35.     int mid;  
  36.     while(low//<  
  37.     {  
  38.         mid&#61;low&#43;((high-low)>>1);  
  39.         if(a[mid]//   
  40.             low&#61;mid&#43;1;  
  41.         else // >&#61;x  
  42.             high&#61;mid;  
  43.     }  
  44.     if(a[low] &#61;&#61; x)  
  45.         return low;  
  46.     return -1;  
  47. }  
  48. /* 
  49. binS_last二分查找返回x(可能有重复)最后一次出现的下标, 
  50. 如无return -1 
  51. low,high 分别为待查元素的区间的 上下界(包含边界). 
  52. x为待查元素.注意 循环结束条件&#xff0c;low&#43;1 &#61;&#61; high */  
  53. int binS_last(int *a, int low, int high, int x)  
  54. {  
  55.     if(NULL &#61;&#61; a || low > high)  
  56.         return -1;  
  57.     int mid;  
  58.     while(low&#43;1//**  
  59.     {  
  60.         mid&#61;low&#43;((high-low)>>1);  
  61.         if(a[mid]<&#61;x) // <&#61;x  
  62.             low &#61; mid;  
  63.         else // >x  
  64.             high&#61;mid-1;  
  65.     }  
  66.     if(a[high] &#61;&#61; x)//先判断high  
  67.         return high;  
  68.     else if(a[low] &#61;&#61;x)return low;  
  69.     return -1;  
  70. }  
  71. int main()  
  72. {  
  73.     int a[]&#61; {-1,1,2,2,2,4,4,4,4,4,4,4}; //0-11  
  74.     printf("-1: %d\n", bin_search(a, 0, 11, -1));  
  75.     printf(" 4 fisrt: %d\n", binS_first(a, 0, 11, 4));  
  76.     printf(" 4 last: %d\n", binS_last(a, 0, 11, 4));  
  77.     printf("\n");  
  78.     int b[]&#61; {-2,-2,0,5,5,7,7}; //0-6  
  79.     printf("-2 fisrt: %d\n", binS_first(b, 0, 6, -2));  
  80.     printf("-2 last: %d\n", binS_last(b, 0, 6, -2));  
  81.     printf(" 5 fisrt: %d\n", binS_first(b, 0, 6, 5));  
  82.     printf(" 5 last: %d\n", binS_last(b, 0, 6, 5));  
  83.     return 0;  
  84. }  



运行结果截图&#xff1a;

                     

此外对于像&#xff0c;二分查找返回刚好小于x的元素下标&#xff0c;二分查找返回刚好大于x的元素下标&#xff0c; 返回有序数列某一个元素重复出现的次数等问题&#xff0c;可以根据上面

的寻找重复元素出现第一次 最后一次位置的方法 进行 问题求解。对于这类问题也可以参考 STL 中关于 lower_bound与upper_bound的实现。STL算法库

中已经有相关实现。

参考&#xff1a;

http://hedengcheng.com/?p&#61;595

编程珠玑

http://blog.csdn.net/daniel_ustc/article/details/17307937


推荐阅读
  • AIX编程挑战赛:AIX正方形问题的算法解析与Java代码实现
    在昨晚的阅读中,我注意到了CSDN博主西部阿呆-小草屋发表的一篇文章《AIX程序设计大赛——AIX正方形问题》。该文详细阐述了AIX正方形问题的背景,并提供了一种基于Java语言的解决方案。本文将深入解析这一算法的核心思想,并展示具体的Java代码实现,旨在为参赛者和编程爱好者提供有价值的参考。 ... [详细]
  • 在嵌入式Linux系统中,性能低下通常由CPU、内存和I/O三个关键因素引起。为了有效提升系统性能,首先需要识别并定位性能瓶颈。通过综合分析这些瓶颈,可以采取针对性的优化措施,如调整内核参数、优化算法和改进数据结构等,从而显著提高系统的整体性能。 ... [详细]
  • 深入解析C语言中的动态规划算法:以背包问题为例
    本文深入探讨了C语言中动态规划算法的应用,以经典的背包问题为例进行详细解析。通过实例分析,展示了如何利用动态规划解决复杂优化问题,并提供了高效的代码实现方法。文章不仅涵盖了算法的基本原理,还讨论了其在实际编程中的应用技巧和优化策略,为读者提供了全面的理解和实践指导。 ... [详细]
  • 在编程笔试和面试中,全排列算法因其适中的难度而备受青睐,不仅能够考察应聘者的算法基础,还能测试其对递归和回溯的理解。本文将深入解析全排列算法的实现原理,探讨其应用场景,并提供优化建议,帮助读者更好地掌握这一重要算法。 ... [详细]
  • 在探讨P1923问题时,我们发现手写的快速排序在最后两个测试用例中出现了超时现象,这在意料之中,因为该题目实际上要求的是时间复杂度为O(n)的算法。进一步研究题解后,发现有选手使用STL中的`nth_element`函数成功通过了所有测试点。本文将详细分析这一现象,并提出相应的优化策略。 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • JavaScript XML操作实用工具类:XmlUtilsJS技巧与应用 ... [详细]
  • Spring框架的核心组件与架构解析 ... [详细]
  • Presto:高效即席查询引擎的深度解析与应用
    本文深入解析了Presto这一高效的即席查询引擎,详细探讨了其架构设计及其优缺点。Presto通过内存到内存的数据处理方式,显著提升了查询性能,相比传统的MapReduce查询,不仅减少了数据传输的延迟,还提高了查询的准确性和效率。然而,Presto在大规模数据处理和容错机制方面仍存在一定的局限性。本文还介绍了Presto在实际应用中的多种场景,展示了其在大数据分析领域的强大潜力。 ... [详细]
  • 本指南从零开始介绍Scala编程语言的基础知识,重点讲解了Scala解释器REPL(读取-求值-打印-循环)的使用方法。REPL是Scala开发中的重要工具,能够帮助初学者快速理解和实践Scala的基本语法和特性。通过详细的示例和练习,读者将能够熟练掌握Scala的基础概念和编程技巧。 ... [详细]
  • 在使用 SQL Server 时,连接故障是用户最常见的问题之一。通常,连接 SQL Server 的方法有两种:一种是通过 SQL Server 自带的客户端工具,例如 SQL Server Management Studio;另一种是通过第三方应用程序或开发工具进行连接。本文将详细分析导致连接故障的常见原因,并提供相应的解决策略,帮助用户有效排除连接问题。 ... [详细]
  • 本文对常见的字符串哈希函数进行了全面分析,涵盖了BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash等多种算法。这些哈希函数在不同的应用场景中表现出各异的性能特点,通过对比其算法原理、计算效率和碰撞概率,为实际应用提供了有价值的参考。 ... [详细]
  • PHP服务接口的专业测试方法与实践 ... [详细]
  • 本课程深入探讨了 Python 中自定义序列类的实现方法,涵盖从基础概念到高级技巧的全面解析。通过实例演示,学员将掌握如何创建支持切片操作的自定义序列对象,并了解 `bisect` 模块在序列处理中的应用。适合希望提升 Python 编程技能的中高级开发者。 ... [详细]
author-avatar
双语的家_352
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有