# 二分总结

[蒋易澄 (小方块)]

二分

二分是每次查找中间值，再根据条件改变搜索区块的算法。
当问题的答案具有某种单调性时，可以用二分查找。
时间复杂度为O(log2n)

二分模板：

1（找第一个，一般用在最小值）

int l = 1, r = n, mid;
while (l < r)
{
  mid = (l + r) / 2;//算出中点
  if (a[mid] >= x)
  {
    r = mid;//向左找
  }
  else
  {
    l = mid + 1;//向右找
  }
}
cout << l;

2（找最后一个， 一般用在最大值）

int l = 1, r = n, mid;
while (l < r)
{
  mid = (l + r + 1) / 2;//算出中点
  if (a[mid] >= x)
  {
    r = mid - 1;//向左找
  }
  else
  {
    l = mid;//向右找
  }
}
cout << l;

做题时if里的条件可以改为check()来判断向左或向右

[李依霄]

好水