# 二分

  • 定义：正常查找是逐个从左到右查找，二分是每次从一半的地方开始查找。一次可以排除一半的元素。

  • 关键：是否具有二段性。

  • 查找大于等于 x 的第一个数

1
2
3
4
5
6
7
8
  
l = 0; r = n-1;
while(l<r>)
{
    int mid=l+r>>1;
    if(a[mid]>=x) r=mid;
    else l=mid+1;
}
  • 查找小于等于 x 的最后一个数
1
2
3
4
5
6
7
8
  
l = 0; r = n-1;
while(l<r)
{
    int mid=l+r+1>>1;
    if(a[mid]<=x) l=mid;
    else r=mid-1;
}
  • 二分题的思路：问满足题意的最大 n 为多少比较难，但是判断 n 能不能满足题意比较简单。因此用循环判断 n 满不满足题意，不断二分求最大 n。

# 尺取

  • 定义：顾名思义，像尺子一样取一段。尺取法通常是保存数组的一对下标，即左右端点，然后根据实际情况不断地推进左右端点以得出答案。

注意事项：

  1. 什么时候可以用尺取法
  2. 何时推进区间端点
  3. 如何推进区间端点
  4. 何时结束区间枚举

# 三分

  • 单峰 / 谷函数：他们有唯一的极值点，且在极值点左右都严格单调且相反。

三分法求极值：

  1. 对于单峰函数 f，在函数定义域 [l,r] 上任取两个点 lmid 和 rmid
  2. 若 f (lmid) < f (rmid), 则 lmid 与 rmid 要么同时处于极大值左侧，要么处于极大值两侧，但是极大值点始终在 lmid 右侧，故可令 l=lmid
  3. 若 f (lmid) > f (rmid), 则 lmid 与 rmid 要么同时处于极大值右侧，要么处于极大值两侧，但是极大值点始终在 rmid 右侧，故可令 r=rmid
  4. 若取 lmid 与 rmid 为三等分点，则每次定义域范围缩小三分之一，通过 log 级别的时间复杂度即可在指定精度下求出极值。