//在arr中区间[lef,rig)寻找第一个>=val的元素的位置
//若没有元素>=val,则返回rig
int lowerBound(int *arr,int lef,int rig,int val)
{
int mid;
while(lef<rig)
{
mid=lef+((rig-lef)>>1);
if(arr[mid]>=val)
{
rig=mid;
}
else lef=mid+1;
}
return lef;
}
//在arr中区间[lef,rig)寻找第一个>val的元素的位置
//若没有元素>val,则返回rig
int upperBound(int *arr,int lef,int rig,int val)
{
int mid;
while(lef<rig)
{
mid=lef+((rig-lef)>>1);
if(arr[mid]<=val)
{
lef=mid+1;
}
else rig=mid;
}
return lef;
}
//在arr中区间[ lef,rig ]寻找等于key的元素
//不存在,则返回-1
int binarySearch(int *arr,int lef,int rig,int key)
{
int mid;
while(lef<=rig)
{
mid=lef+(rig-lef)/2;
if(arr[mid]==key) return mid;
if(arr[mid]>key) rig=mid-1;
else lef=mid+1;
}
return -1;
}
网友评论