当前位置: 开发笔记 > 编程语言 > 正文

二分查找（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

/*
bin_search 二分查找元素x的下标&＃xff0c;如无 return -1
low,high 分别为待查元素的区间的上下界(包含边界).
x为待查元素.
注意 low <&＃61; high
*/
int bin_search(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)
return -1;
int mid;
while(low<&＃61;high)//注意是<&＃61;&＃xff0c;若是<会找不到边界值情况
{
mid &＃61; low &＃43; ((high-low)>>1);
if(x
high &＃61; mid-1;
else if(x>a[mid])
low &＃61; mid &＃43;1;
else
return mid;
}
return -1;
}

对于问题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

/*
binS_first二分查找返回x(可能有重复)第一次出现的下标&＃xff0c;如无return -1
low,high 分别为待查元素的区间的上下界(包含边界).
//分成2个序列:[first,mid][mid&＃43;1,last)
x为待查元素.注意循环结束条件&＃xff0c;low &＃61;&＃61; high */
int binS_first(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)return -1;
int mid;
while(low
{
mid&＃61;low&＃43;((high-low)>>1);//计算中点
if(a[mid]//
low&＃61;mid&＃43;1;
else // >&＃61;x
high&＃61;mid;
}
if(a[low] &＃61;&＃61; x)
return low;
return -1;
}

对于问题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

/*
binS_last二分查找返回x(可能有重复)最后一次出现的下标,如无return -1
low,high 分别为待查元素的区间的上下界(包含边界).
x为待查元素.
注意循环结束条件&＃xff0c;low&＃43;1 &＃61;&＃61; high
*/
int binS_last(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)
return -1;
int mid;
while(low&＃43;1//**
{
mid&＃61;low&＃43;((high-low)>>1);
if(a[mid]<&＃61;x) // <&＃61;x
low &＃61; mid;
else // >x
high&＃61;mid-1;
}
if(a[high] &＃61;&＃61; x)//先判断high
return high;
else if(a[low] &＃61;&＃61; x)
return low;
return -1;
}

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

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

总的测试程序。

[cpp] view plaincopy

#include
/*
bin_search 二分查找元素x的下标&＃xff0c;如无 return -1
low,high 分别为待查元素的区间的上下界(包含边界).
x为待查元素.
注意 low <&＃61; high
*/
int bin_search(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)
return -1;
int mid;
while(low<&＃61;high)//注意是<&＃61;&＃xff0c;若是<会找不到边界值情况
{
mid &＃61; low &＃43; ((high-low)>>1);
if(x
high &＃61; mid-1;
else if(x>a[mid])
low &＃61; mid &＃43;1;
else
return mid;
}
return -1;
}
/*
binS_first二分查找返回x(可能有重复)第一次出现的下标,如无return -1
low,high 分别为待查元素的区间的上下界(包含边界).
//分成2个序列:[first,mid][mid&＃43;1,last)
x为待查元素.
注意循环结束条件&＃xff0c;low &＃61;&＃61; high */
int binS_first(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)return -1;
int mid;
while(low//<
{
mid&＃61;low&＃43;((high-low)>>1);
if(a[mid]//
low&＃61;mid&＃43;1;
else // >&＃61;x
high&＃61;mid;
}
if(a[low] &＃61;&＃61; x)
return low;
return -1;
}
/*
binS_last二分查找返回x(可能有重复)最后一次出现的下标,
如无return -1
low,high 分别为待查元素的区间的上下界(包含边界).
x为待查元素.注意循环结束条件&＃xff0c;low&＃43;1 &＃61;&＃61; high */
int binS_last(int *a, int low, int high, int x)
{
if(NULL &＃61;&＃61; a || low > high)
return -1;
int mid;
while(low&＃43;1//**
{
mid&＃61;low&＃43;((high-low)>>1);
if(a[mid]<&＃61;x) // <&＃61;x
low &＃61; mid;
else // >x
high&＃61;mid-1;
}
if(a[high] &＃61;&＃61; x)//先判断high
return high;
else if(a[low] &＃61;&＃61;x)return low;
return -1;
}
int main()
{
int a[]&＃61; {-1,1,2,2,2,4,4,4,4,4,4,4}; //0-11
printf("-1: %d\n", bin_search(a, 0, 11, -1));
printf(" 4 fisrt: %d\n", binS_first(a, 0, 11, 4));
printf(" 4 last: %d\n", binS_last(a, 0, 11, 4));
printf("\n");
int b[]&＃61; {-2,-2,0,5,5,7,7}; //0-6
printf("-2 fisrt: %d\n", binS_first(b, 0, 6, -2));
printf("-2 last: %d\n", binS_last(b, 0, 6, -2));
printf(" 5 fisrt: %d\n", binS_first(b, 0, 6, 5));
printf(" 5 last: %d\n", binS_last(b, 0, 6, 5));
return 0;
}

运行结果截图&＃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

推荐阅读

schema
如何使用Maven将依赖插件一并打包进JAR文件

本文详细介绍了在使用Maven构建项目时，如何将所需的依赖插件一同打包进最终的JAR文件中，以避免手动部署依赖库的麻烦。 ... [详细]

蜡笔小新 2024-11-23 22:51:34
python
将XML数据迁移至Oracle Autonomous Data Warehouse (ADW)

随着Oracle ADW的推出，数据迁移至ADW成为业界关注的焦点。特别是XML和JSON这类结构化数据的迁移需求日益增长。本文将通过一个实际案例，探讨如何高效地将XML数据迁移至ADW。 ... [详细]

蜡笔小新 2024-11-23 20:27:56
string
必须为元素类型 mapper 声明属性 namespace解决

在使用mybatis进行mapper.xml测试的时候发生必须为元素类型“mapper”声明属性“namespace”的错误项目目录结构UserMapper和UserMappe ... [详细]

蜡笔小新 2024-11-23 20:06:58
js
SSM框架实战：分页功能实现详解

本文详细介绍如何在SSM（Spring + Spring MVC + MyBatis）框架中实现分页功能。包括分页的基本概念、数据准备、前端分页栏的设计与实现、后端分页逻辑的编写以及最终的测试步骤。 ... [详细]

蜡笔小新 2024-11-23 11:40:33
byte
【MySQL】frm文件解析

官网说明：http:dev.mysql.comdocinternalsenfrm-file-format.htmlfrm是MySQL表结构定义文件，通常frm文件是不会损坏的，但是如果 ... [详细]

蜡笔小新 2024-11-23 10:29:06
js
41款高效LISP工具助力数据处理全流程

本文由公众号【数智物语】(ID: decision_engine)发布，关注获取更多干货。文章探讨了从数据收集到清洗、建模及可视化的全过程，介绍了41款实用工具，旨在帮助数据科学家和分析师提升工作效率。 ... [详细]

蜡笔小新 2024-11-24 00:11:50
js
MySQL 高级特性深度解析

本文深入探讨了MySQL中的高级特性，包括索引机制、锁的使用及管理、以及如何利用慢查询日志优化性能。适合有一定MySQL基础的读者进一步提升技能。 ... [详细]

蜡笔小新 2024-11-23 22:01:49
string
利用Scrapy构建的数据采集与分析可视化系统

本文探讨了如何使用Scrapy框架构建高效的数据采集系统，以及如何通过异步处理技术提升数据存储的效率。同时，文章还介绍了针对不同网站采用的不同采集策略。 ... [详细]

蜡笔小新 2024-11-23 16:56:38
php
LaTeX高级应用技巧

本文分享了作者在使用LaTeX过程中的几点心得，涵盖了从文档编辑、代码高亮、图形绘制到3D模型展示等多个方面的内容。适合希望深入了解LaTeX高级功能的用户。 ... [详细]

蜡笔小新 2024-11-23 12:47:16
php
MVC模式下的电子取证技术初探

本文探讨了在MVC（模型-视图-控制器）架构下进行电子取证的技术方法，通过实际案例分析，提供了详细的取证步骤和技术要点。 ... [详细]

蜡笔小新 2024-11-23 12:13:06
python
深入理解iOS中的链式编程：以Masonry为例

本文通过介绍Masonry这一轻量级布局框架，探讨链式编程在iOS开发中的应用。Masonry不仅简化了Auto Layout的使用，还提高了代码的可读性和维护性。 ... [详细]

蜡笔小新 2024-11-23 12:02:10
stream
Python 实现监控与运维自动化方案

本文探讨了使用Python实现监控信息收集的方法，涵盖从基础的日志记录到复杂的系统运维解决方案，旨在帮助开发者和运维人员提升工作效率。 ... [详细]

蜡笔小新 2024-11-23 11:25:14
string
数据输入验证与控件绑定方法

本文提供了多种数据输入验证函数及控件绑定方法的实现代码，包括电话号码、数字、传真、邮政编码、电子邮件和网址的验证，以及报表绑定和自动编号等功能。 ... [详细]

蜡笔小新 2024-11-23 07:47:36
string
MySQL窗口函数详解与应用

本文介绍了MySQL窗口函数的基本概念、应用场景及常见函数的使用方法。窗口函数在处理复杂查询时非常有用，例如计算每个用户的订单排名、环比增长率、以及动态聚合等。 ... [详细]

蜡笔小新 2024-11-23 02:53:38
schema
binlog2sql，你该知道的数据恢复工具

binlog2sql，你该知道的数据恢复工具 ... [详细]

蜡笔小新 2024-11-22 18:58:43

双语的家_352

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章