二分板子:
四种情况:
1.查找第一个大于等于某元素的下标
//注意这里l和r的初始值也不能随便改
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= x) r = mid; //若当前数已经大于等于,在左边区间看看有没有更小的大于等于它的数
else l = mid + 1;
}
2.查找第一个(又或者说是最后一个)小于等于某元素的下标
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
//若当前数已经小于等于,在右边区间看有没有更大的小于等于它的数
else r = mid - 1;
}
3.查找第一个大于某元素的下标
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] > x) r = mid; //若当前数已经大于等于,在左边区间看有没有更小的大于它的数
else l = mid + 1;
}
4.查找第一个小于某元素的下标
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] < x) l = mid;
//若当前数已经小于等于,在右区间看有没有更大的小于它的数
else r = mid - 1;
}
5.另外,判断找没找到只需要加一个flag用来判断
注意!!注意!!用flag判断有时会有边界问题!!!
例如:在else中由l = mid + 1致使 l == r跳出循环,此时若a[r] >= x,则也是查找成功
比如:
int flag = -1;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= x)
{
flag = mid;
r = mid;
}
//若当前数已经大于等于,在左边区间看看有没有更小的大于等于它的数
else l = mid + 1;
}