折半查找——一不小心，又是一个坑。。。

本文主要是介绍折半查找——一不小心，又是一个坑。。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自黑暗之神

折半查找这题本来以为就能一A的。。。想不到却提交了那么多次
却一直WA 检查了半天算法，却也没有发现问题，知道最后才猛的想到
输入的数可能是会有重复的
比如
4 3
1 1 2 4
1 3 4
如果按题中所给的算法，得出的便是 1 -1 3
而答案所想要的是0 -1 3（虽然它压根就没有告诉你。。。。-_-|||）
即答案所想要的是
等于 v 的第一个值

下附上两种算法
1，普通二分查找

int bs(int a[],int l,int h,int v)
{
int m;
while(l<h)
{
m=(l+h)>>1;//移位，即相当于除以2
if(a[m]==v)
return m;（关键问题就出在这里了有木有！！！！！仔细想一下！）
if(a[m]<v)
l=m+1;
else
h=m;
}
return -1;
}

2,等于v的第一个值
int lower_bound(int a[],int l,int h,int v)
{
int m;
while(l<h)
{
m=(l+h)>>1;
if(a[m]>=v)
{
h=m;
}
else
{
l=m+1;
}
}
if(v==arr[l])
{
return l;
}
return -1;
}

折半查找其实还可以用来处理上下界问题

例如求下界

int lower_bound(int a[],int l,int h,int v)
{
int m;
while(l<h)
{
m=(l+h)>>1;
if(a[m]>=v)
{
   h=m;
}
else
{
   l=m+1;
}
}
return l;
}
求上界
int upper_bound(int a[],int l,int h,int v)
{
int m;
while(l<h)
{
m=(l+h)>>1;
if(a[m]>v)
{
   h=m;
}
else
{
   l=m+1;
}
}
return l;
}

两个程序直接的差距其实就是等号所在的区域不同而已

最后补充一点
STL库中有专门的函数可以调用
如 upper_bound(a,a+n,v)
lower_bound(a,a+n,v)

这篇关于折半查找——一不小心，又是一个坑。。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！