四个二分万能模板汇总（精简版）

精简版）"/>

四个二分万能模板汇总（精简版）

模板来源

b站教程：二分查找为什么总是写错？_哔哩哔哩_bilibili

模板

int l=-1,r=N;
while(l+1!=r)
{int mid=(l+r)/2;if(check)l=mid;else r=mid;
}
return l or r;

四种情况：

1.找到第一个大于x的元素

check:q[mid]<=x

return:r

2.找到第一个大于等于x的元素

check:q[mid]<x

return:r

3.找到最后一个小于x的元素

check:q[mid]<x

return:l

4.找到最后一个小于等于x的元素

check:q[mid]<=x

return:r

演示

“数的范围”：比如一段序列3 4 4 5 5 5 6

5的下标范围为[3,5]

左边界即找：大于等于5的第一个下标

右边界即找：小于等于5的最后一个下标

对应代码分别为：

int l=-1,r=N;
while(l+1!=r)
{int mid=(l+r)/2;if(q[mid]<x)l=mid;else r=mid;
}
return r;int l=-1,r=N;
while(l+1!=r)
{int mid=(l+r)/2;if(q[mid]<=x)l=mid;else r=mid;
}
return l;