由于本人经常被二分与三分的各种细节卡死，所以记录一下。 二分如果出错了，注意查看二分的初始范围、二分的判断条件、L/R的赋值、最终二分得到的结果等。有时候二分错误并不是因为二分细节问题，而是题目存在边界，需要特判。

 

二分：

目前常用的二分有3种写法，区别在于：①闭区间或左闭右开区间  ②退出条件时l==r？或l==r+1

（1）写法一，左闭右开/左开右闭区间，最终l==r 

int l = 1, r = n + 1, mid; // 对应区间 [l, r)
while (l < r) {
  mid = (l + r) >> 1;
  if (OK(mid)) r = mid;  // 如果mid是OK的，区间变为[l,mid]
  else l = mid + 1;  // 否则变为[mid+1,r]
}
// 另一种写法
int l = 0, r = n, mid; // 对应区间 (l, r]
while (l < r) {
  mid = (l + r + 1) >> 1;
  if (OK(mid)) l = mid;
  else r = mid - 1;
}

个人比较习惯使用这种方法。

1. 上面给出两种写法，区别就：\(mid\) 已经是合法的了，但是希望找到 更小/更大 的 \(ans\)。所以在写代码的时候，就可以关心于 \(check \space mid\) 的值是不是合法的，然后选择让他变大还是变小。

2. 还有一个细节就是初始区间。以左闭右开为例，二分可能会枚举到的范围只有：\([l,r-1]\)，所以不用担心 \(r\) 合不合法。如果不断变大，最后 \(l\) 和 \(r\) 都变成右边界。   

 

（2）写法二，闭区间，最终l==r+1，但是碍于边界问题正确的答案应该是\( l \) 。

int l = 1, r = n, mid; // 对应区间 [l, r]
while (l <= r) {
  mid = (l + r) >> 1;
  if (a[mid] <= target) r = mid - 1;  // 返回的结果和等号=所处位置有关
  else l = mid + 1;
}

比如说： \( a = {1,3,3,5} \)。

例一：我们模拟在 \( a \) 数组中找 \( 100 \) ，那么肯定返回的是 \( l == 5 , r == 4 \)

　　搜索过程： \( l=1,r=4,mid=2 \) -> \( l=3,r=4,mid=3 \) -> \( l=4,r=4,mid=4 \) -> \( l=5,r=4,break \)。

例二： 如果找 \( 0 \)的话，按上面过程，得出的就是 \( l=1,r=0 \) ，如果是 \(lowerbound\) ，那么l=1无疑是对的。

例三：如果我们找的是3呢？ 【假设相等时，令r=mid-1】

　　搜索过程： \( l=1,r=4,mid=2 \) -> \(l=1,r=1,mid=1\) -> \( l = 2,r=1,break \) 这时的结果仍然是 \(lowerbound\) 的

　　但是我们如果 \( a[mid] == target \) 时，让 \( l = mid + 1\) 会怎么样？

　　搜索过程：\( l=1,r=4,mid=2 \) -> \( l = 3,r = 4,mid = 3\) -> \( l = 4,r = 4,mid = 4\) -> \( l=4,r=3,break\)

这个时候结果就是 \(upperbound\) 了，所以使用这种方法时，一定要特别注意等号的位置。 

但你时常会见到这样的写法：其中的 \(INIT\_ANS\) 取决于如果搜不到合法值，你必须设定的值。

int l = 1, r = n, mid, ans = INIT_ANS;
while (l <= r) {
  mid = (l + r) / 2;
  if (ok(mid)) ans = mid, l = mid + 1;
  else r = mid - 1; 
}
cout << ans << endl;

 

 

（3）写法三，闭区间，最终 l + 1 == r ，也就是说，区间内剩下两个数就退出了

while(l + 1 < r) {
  mid = (l + r) >> 1;
  if(OK(mid)) r = mid;
  else l = mid;
}

这三种写法各有优略，第一种是 \(st\) l的 \(lower_bound\) 使用的，第二种目前没找到特殊用法，但是第三种能维护的东西是前两者不能维护的。

比如说：有些题目就是维护间隔的信息，那么应该使用第三种写法。因为 \( [ mid-1 , mid, mid+1 ] \) 三个数之间有两个间隔，我们要舍去另一半的时候，我们应该舍去的是间隔，而不是mid。若舍去的是\( [mid-1, mid] \) ，应该保留的是 \( [mid, mid+1] \) 。所以最后区间剩下的是两个数，也就是一个间隔。【这道题就是这么做的：LINK （欧拉序 + 二分） 其它写法也可做】

 

参考资料：知乎-二分查找有几种方法?

比较喜欢文章里面的一句话：二分无非就是寻找到 \(lower\_bound - 1 、lower\_bound 、 upper\_bound - 1 、 upper\_bound\) 四个值中的一个。 

 

 

 

三分：

 三分咕了。没怎么仔细研究过三分。

int l = 1, r = n, lmid, rmid;
while (l <= r) {
  lmid = l + (r - l) / 3;
  rmid = r - (r - l) / 3;
  if (value(lmid) < value(rmid)) l = lmid + 1;
  else r = rmid - 1;
}
return l or r;