## 基本思想:二分
易错点:边界问题(+1问题)
----------
## 本质
有某一个种性质,将整个区间一分为二,就可二分出边界点,所以就产生了两个边界点。
## 例如
3 6 6 9 10 求取6的起始坐标
mid =(0+5-1)/2=2
起始位置更新获取6的位置,长度缩小一半为 3 6 6
然后末位置更新获取6位置(先确定边界与性质)
有可能有一些情况又无解的,但是二分一定是有解的,这个问题是题目问题
代码模板解释
bool check(int x) {}
// 检查x是否满足某种性质,更新区间
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
//更新 l,r
if (check(mid)) r = mid;
// check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
//+1->为了解决l,r更新失败(死循环)问题
int mid = l + r + 1 >> 1;
//更新 l,r
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
模板
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
}
```