lower_bound实现函数

lower_bound实现

【参考链接】[ **lower_bound二分的三种写法**]( http://blog.csdn.net/binling/article/details/42361551)

我在以前,总是用lower_bound,现在发现这样不行,有些复杂的数据结构二分的时候用这个会很麻烦,不如手写二分,我接着就查了下资料,发现并不难。

我下面这个代码写的是lower_bound,其实稍微改下就可以变成upper_bound了,下面我给出分别2个版本的代码:

&代码lower_bound:

//二分的区间是a[]数组里的[l,r] 找的是tar
int lowbou(int a[],int l,int r,int tar)
{
while(l<=r){
int mid=(l+r)/2;
if (a[mid]<tar) l=mid+1;
else r=mid-1;
}
return l;
}

&代码upper_bound:

//二分的区间是a[]数组里的[l,r] 找的是tar
int uppbou(int a[],int l,int r,int tar)
{
while(l<=r){
int mid=(l+r)/2;
if (a[mid]<=tar) l=mid+1;
else r=mid-1;
}
return l;
}

我建议先把第一个lower_bound的多敲几遍,记下来,之后多写一个"="号就是upper_bound了。注意:不管那种,最后return的都是l,不是r

lower_bound:中间if判断是 if (a[mid] < tar)

upper_bound:中间if判断是 if (a[mid] <= tar)

上一篇:类Arrays


下一篇:eclipse各种操作指南