二分查找算法在C/C++程序中的应用示例
作者:wuzhekai1985 发布时间:2021-06-01 08:15:30
二分查找算法的思想很简单,《编程珠玑》中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题。开始时,范围就是整个数组。通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小。这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空。
Donald Knuth在他的《Sorting and Searching》一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来。其中常见的一个bug是对中间值下标的计算,如果写成(low+high)/2,当low+high很大时可能会溢出,从而导致数组访问出错。改进的方法是将计算方式写成如下形式:low+ ( (high-low) >>1)即可。下面给出修改后的算法代码:
int binarysearch1(int a[],int n,int x)
{
int l,u,m;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
else if(x==a[m])
return m;
else
l=m+1;
}
return -1;
}
这里注意一点,由于使用的是不对称区间,所以下标的调整看上去有点不规整。一个是u=m,另一个是l=m+1。其实很好理解,调整前区间的形式应该是 [ )的形式,如果中间值比查找值小,那么调整的是左边界,也就是闭的部分,所以加1;否则,调整是右边界,是开的部分,所以不用减1。调整后仍是[ )的形式。当然也可以写成对称的形式。代码如下:
int binarysearch1(int a[],int n,int x)
{
int l,u,m;
l=0;u=n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m-1;
else if(x==a[m])
return m;
else
l=m+1;
}
return -1;
}
这样也看上去比较规整,但是有个不足。如果想把程序改成“纯指针”的形式,就会有麻烦。修改成纯指针的代码如下:
int binarysearch2(int *a,int n,int x)
{
int *l,*u,*m;
l=a;u=a+n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m-1;
else if(x==*m)
return m-a;
else
l=m+1;
}
return -1;
}
当n为0时,会引用无效地址。而用非对称区间则不会有这个问题。代码如下:
int binarysearch2(int *a,int n,int x)
{
int *l,*u,*m;
l=a;u=a+n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m;
else if(x==*m)
return m-a;
else
l=m+1;
}
return -1;
}
上面给出的二分查找是迭代法实现,当然也可以用递归的方式实现。代码如下:
int binarysearch3(int a[],int l,int u,int x)
int m=l+((u-l)>>1);
if(l<=u)
{
if(x<a[m])
return binarysearch3(a,l,m-1,x);
else if(x==a[m])
return m;
else
return binarysearch3(a,m+1,u,x);
}
return -1;
上述这些二分算法,若数组元素重复,返回的是重复元素的某一个元素。如果希望返回被查找元素第一次出现的位置,则需要修改代码。下面给出了一种解法:
int binarysearch4(int a[],int n,int x)
{
int l,u,m;
int flag=-1;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
else if(x==a[m])
flag=u=m;
else
l=m+1;
}
return flag;
}
下面是《编程珠玑》上的解法:
int binarysearch4(int a[],int n,int x)
{
int l,u,m;
l=-1;u=n;
while(l+1<u)
{
m=l+((u-l)>>1);
if(a[m]<x)
l=m;
else
u=m;
}
return (u>=n||a[u]!=x)?-1:u;
}
至此二分算法的代码讨论结束,下面讨论一下程序的测试问题。《代码之美》有一章专门介绍二分查找算法的测试,非常漂亮。这里班门弄斧,简单给出几个测试用例。针对binarysearch1。测试程序如下:
#include <iostream>
#include <cassert>
#include <algorithm>
#include <ctime>
using namespace std;
int calmid(int l,int u) { return l+((u-l)>>1); }
int binarysearch1(int a[],int n,int x);
#define bs1 binarysearch1
int main()
{
long start,end;
start=clock();
int a[9]={-2147483648,-13,-10,-5,-3,0,1,400,2147483647};
//中值下标计算的测试
assert(calmid(0,1)==0);
assert(calmid(0,2)==1);
assert(calmid(1000000,2000000)==1500000);
assert(calmid(2147483646,2147483647)==2147483646);
assert(calmid(2147483645,2147483647)==2147483646);
//冒烟测试
assert(bs1(a,9,0)==5);
assert(bs1(a,9,1)==6);
assert(bs1(a,9,2)==-1);
//边界测试
assert(bs1(a,0,1)==-1); //0个元素
assert(bs1(a,1,-2147483648)==0); //1个元素 成功
assert(bs1(a,1,-2147483647)==-1); //1个元素 失败
assert(bs1(a,9,-2147483648)==0); //首个元素
assert(bs1(a,9,-3)==4); //中间元素
assert(bs1(a,9,2147483647)==8); //末尾元素
//自动化测试
int b[10000];
int i,j;
for(i=0;i<10000;i++)
{
b[i]=i*10;
for(j=0;j<=i;j++)
{
assert(bs1(b,i+1,j*10)==j);
assert(bs1(b,i+1,j*10-5)==-1);
}
}
//自动化测试 引入随机数
srand(time(0));
for(i=0;i<10000;i++)
{
b[i]=rand()%1000000;
sort(&b[0],&b[i]);
for(j=0;j<=i;j++)
{
int x=rand();
int k=bs1(b,i+1,x);
if(k!=-1)
assert(b[k]==x);
}
}
end=clock();
cout<<(end-start)/1000.0<<'s'<<endl;
return 0;
}
注意到数组的元素有正数,负数,零,最大值,最小值。通常会忘掉负数的测试,引入最大值和最小值,主要是为了边界测试。
第一,测试了中值下标的计算。另外写了一个小函数,单独测试。考虑到内存可能放不下这么大的数组,因此只是模拟测试,并没有真正申请这么大的空间,但是对于中值下标的测试足够了。
第二,冒烟测试。即做一些最基本的测试。测试通过后进行边界测试。
第三,边界测试。这里有三种类型,一是针对数组元素个数,分别是0个,1个。二是针对元素位置,分别是首个元素,中间元素,末尾元素。三是针对元素值,有最大值,最小值,0等测试。
第四,自动化测试。这里自动生成测试的数组,然后针对每个元素进行成功查找测试。
第五,自动化测试,只不过数组的元素是随机值。
第五,性能测试。这里相关代码没有列出。以上测试都通过时,可以修改查找算法,添加性能测试的代码。其实可以简单添加一个比较的计数器。返回值从原来的查找结果改为比较的计数器值即可。代码比较简单,就不列了。
Note:二分查找容易忽略的一个bug
对于二分查找算法,相信大家肯定不会陌生。算法从一个排好序的数组中找指定的元素,如果找到了返回该元素在数组中的索引,否则返回-1。下面给出了解法。
//a为排好序的数组,n为数组的大小,x为指定元素
int binarySearch(int a[], int n, int x)
{
int left = 0, right = n-1, middle = 0;
int tmp = 0;
while(left <= right)
{
middle = (left + right)/2;
tmp = a[middle];
if(x < tmp) right = middle - 1;
else if(x > tmp) left = middle + 1;
else return middle;
}
return -1;
}
乍看没有错误,但是不幸的是,该程序存在一个bug。当数组极大时,(left+right)可能为负数,则数组下标溢出,程序崩溃。
解决的方案:将middle=(left+right)/2改为middle=left+(right-left)/2即可。即利用减法代替加法,从而消除上溢。
参考自《代码之美》
猜你喜欢
- 一、使用ThreadLocal实现当前登录信息的存取在项目中我们增加一个员工有一些信息是需要我们自己填入的,有一些信息不需要我们自己填写,例
- 本文实例讲述了C#微信公众号开发之接收事件推送与消息排重的方法。分享给大家供大家参考。具体分析如下:微信服务器在5秒内收不到响应会断掉连接,
- 原理简介Java中提供了Calendar这个专门用于对日历进行操作的类,那么这个类有什么特殊的地方呢,首先我们来看Calendar的声明:p
- 前言Java 中的 synchronized关键字可以在多线程环境下用来作为线程安全的同步锁。本文不讨论 synchronized 的具体使
- TTL简介TTL 是什么呢?TTL 是 RabbitMQ 中一个消息或者队列的属性,表明一条消息或者该队列中的所有消息的最大存活时间,单位是
- 1. mapper.xml设置resultTyperesultType="com.alibaba.fastjson.JSONObj
- Java8对List<Integer>的求和想要用流对List<Integer>进行求和,但查找完资料都是对List
- 本文实例为大家分享了C#实现飞行棋的具体代码,供大家参考,具体内容如下游戏规则如果玩家A踩到了玩家B,玩家B退6格踩到了1幸运轮盘,a交换位
- 第一个SpringMvc HelloWorld无启动类springboot才有启动类前端操作访问项目名进入默认主页,显示一个链接点击链接后请
- 一,使用背景之前遇到一个需求,是需要将一个json文件解析存储到数据库中。一开始测试的时候,json文件的大小都在几兆以内,所以直接将jso
- 本文实例讲述了Windows窗体的.Net框架绘图技术实现方法,非常实用,具体内容如下:一般来说,当编写一个典型的Windows 窗体程序时
- 使用 try/catch 处理异常try-catch 块的用途是捕捉和处理工作代码所生成的异常。 有些异常可以在 catch 块中处理,解决
- 注意是maven的webapp:选择maven下一步下一步。maven下载过慢在setting中加入镜像。 我也有疑问这是什么鬼格式,但是证
- Android WebView 1.首先修改activity.xml中的代码:2.然后MainActivity中的代码:3.最后设置权限:&
- 前言很多人觉得Xamarin的开源少,没法用来开发项目。但,实际上Xamarin已经有很多开源代码了;只要不是特别特殊的项目,基本上是都可以
- 传统的Trie实现简单,但是占用的空间实在是难以接受,特别是当字符集不仅限于英文26个字符的时候, * 起来的空间根本无法接受。双数组Trie
- 引言JVM进程消失可能有哪些原因?这个问题也是面试中经常出现的,如下图所示ps:由于两年多没写crud了,所以忘记mybatis怎么用了,所
- 条码的应用已深入生活和工作的方方面面。在处理条码时,常需要和各种文档格式相结合。当需要在文档中插入、编辑或者删除条码时,可借助于一些专业的类
- 简介本文主要介绍如何使用java代码利用Selenium操作浏览器,某些网页元素加载慢,如何操作元素就会把找不到元素的异常,此时需要设置元素
- 如下所示://定义二维数组写法1 class numthree{public static void main(String[] args)