二分法又可以分为整数二分和实数二分

整数二分

使用二分的目的是寻找到某一个符合要求的数，因为数量的庞大，不可能把整个数组全部都遍历，所以使用二分来减少算法的复杂度。

基本思路

在一个区间的内部，来寻找边答案所在的区间，在这个区间里面继续缩小区间。
当区间的长度是一的时候区间里面的就是所求的答案
二分模板一定是有解的，（即定义的性质一定是有边界的），但是不一定是题目需求的答案，这时根据题目判断有没有解。

简单来说
假设目标值在闭区间中，[l, r] 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

下面就是两种模板：
1. 当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  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;
  }
2. 当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  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;
  }
  记住这两个模板就可以应对基本所有的二分题目了
浮点数的二分
浮点数的二分比整数的二分简单，不用考虑边界设置导致的死循环

唯一需要注意的是结束二分的条件的改变。

从l == r变为判断浮点数的差值 r - l < 1e-6

注意：
一般设置判断差值的时候将，设置为比题目要求更往后的两位，来保证答案的准确性。

代码模板：
1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
while ( r - l < 1e-6)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid ;
}
return l;
}

SnowDawn'Home

二分模板（坑）

二分法又可以分为整数二分和实数二分

整数二分

基本思路

简单来说

浮点数的二分

注意：