lower_bound实现函数

lower_bound实现

【参考链接】[ **lower_bound二分的三种写法**]( http://blog.****.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)