首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

二分查找（BinarySearch）常见问题解决方法总结

作者：双语的家_352 | 来源：互联网 | 2023-10-16 09:22
缘由今天浏览何登成的技术博客无意中发现了写的blog，二分查找(BinarySearch)需要注意的问题，以及在数据库内核中的实现。随想总结下二分查找的

缘由

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

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

问题背景

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

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

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

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

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

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

二分查找算法的思想

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

而想要应用二分查找法&＃xff0c;这“一堆数”必须有一下特征&＃xff1a;

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

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

其实二分查找算法的思想很简单&＃xff0c;在《编程珠玑》一书中的描述&＃xff1a;

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

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

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

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

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

写成如下形式&＃xff1a;low&＃43; ( (high-low) >>1)。

常见问题解决

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

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

主要是下面三个问题&＃xff1a;

1&＃xff09;二分查找元素x的下标&＃xff0c;如无 return  -1

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

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

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

代码如下&＃xff1a;

[cpp] view plaincopy
  1. /*  
  2. bin_search 二分查找元素x的下标&＃xff0c;如无 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


推荐阅读
  • select

    数据库的存储结构及其重要性

    本文介绍了数据库的存储结构及其重要性，强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离，可以实现对物理存储的重新组织和数据库的迁移，而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构，并介绍了表空间的概念和作用。 ... [详细]
  • select

    [译]技术公司十年经验的职场生涯回顾

    [译]技术公司十年经验的职场生涯回顾
    本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同，令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望，认为人类有能力不断改善自己。 ... [详细]
  • select

    图解redis的持久化存储机制RDB和AOF的原理和优缺点

    图解redis的持久化存储机制RDB和AOF的原理和优缺点
    本文通过图解的方式介绍了redis的持久化存储机制RDB和AOF的原理和优缺点。RDB是将redis内存中的数据保存为快照文件，恢复速度较快但不支持拉链式快照。AOF是将操作日志保存到磁盘，实时存储数据但恢复速度较慢。文章详细分析了两种机制的优缺点，帮助读者更好地理解redis的持久化存储策略。 ... [详细]
  • string

    《数据结构》学习笔记3——串匹配算法性能评估

    《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • main

    Java中vector的使用详解

    本文详细介绍了Java中vector的使用方法和相关知识，包括vector类的功能、构造方法和使用注意事项。通过使用vector类，可以方便地实现动态数组的功能，并且可以随意插入不同类型的对象，进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下，使用vector类是一个很好的选择。 ... [详细]
  • lua

    lua语言闭包、模式匹配、日期、编译、模块的特性及应用

    本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]
  • lua

    云原生边缘计算之KubeEdge简介及功能特点

    云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • format

    C#学习教程：在Console中工作但在Windows窗体中不工作的异步代码分享

    本文分享了一个关于在C#中使用异步代码的问题，作者在控制台中运行时代码正常工作，但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机，但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]
  • grid

    PhysioNet生理信号处理（三）WFDB Toolbox for Matlab的安装和使用方法

    本文介绍了PhysioNet网站提供的生理信号处理工具箱WFDB Toolbox for Matlab的安装和使用方法。通过下载并添加到Matlab路径中或直接在Matlab中输入相关内容，即可完成安装。该工具箱提供了一系列函数，可以方便地处理生理信号数据。详细的安装和使用方法可以参考本文内容。 ... [详细]
  • grid

    解决Cydia数据库错误：could not open file /var/lib/dpkg/status 的方法

    解决Cydia数据库错误：could not open file /var/lib/dpkg/status 的方法
    本文介绍了解决iOS系统中Cydia数据库错误的方法。通过使用苹果电脑上的Impactor工具和NewTerm软件，以及ifunbox工具和终端命令，可以解决该问题。具体步骤包括下载所需工具、连接手机到电脑、安装NewTerm、下载ifunbox并注册Dropbox账号、下载并解压lib.zip文件、将lib文件夹拖入Books文件夹中，并将lib文件夹拷贝到/var/目录下。以上方法适用于已经越狱且出现Cydia数据库错误的iPhone手机。 ... [详细]
  • get

    计算机存储系统的层次结构及其优势

    计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构，包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体，形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低，使得整体存储系统的平均价格降低。同时，高速缓存的存取速度可以和CPU的工作速度相匹配，进一步提高程序执行效率。 ... [详细]
  • grid

    不同优化算法的比较分析及实验验证

    不同优化算法的比较分析及实验验证
    本文介绍了神经网络优化中常用的优化方法，包括学习率调整和梯度估计修正，并通过实验验证了不同优化算法的效果。实验结果表明，Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ... [详细]
  • main

    动态规划算法的基本步骤及最长递增子序列问题详解

    动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]
  • require

    Android系统移植与调试之如何修改Android设备状态条上音量加减键在横竖屏切换的时候的显示于隐藏

    Android系统移植与调试之如何修改Android设备状态条上音量加减键在横竖屏切换的时候的显示于隐藏
    本文介绍了如何修改Android设备状态条上音量加减键在横竖屏切换时的显示与隐藏。通过修改系统文件system_bar.xml实现了该功能，并分享了解决思路和经验。 ... [详细]
  • require

    开发笔记:计网局域网：NAT 是如何工作的？

    开发笔记:计网局域网：NAT 是如何工作的？
    篇首语：本文由编程笔记#小编为大家整理，主要介绍了计网-局域网：NAT是如何工作的？相关的知识，希望对你有一定的参考价值。 ... [详细]
author-avatar
双语的家_352
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有