整数二分算法

整数二分算法
难点：整数二分的边界问题（这个很棘手，因为写得不好容易造成死循环）。

二分的本质：
有单调性一定可以二分，但没有单调性也有可能可以二分。二分的本质不是单调性。
二分的本质是边界：整个区间可以一分为二，一半满足某个性质，一半不满足。 二分可以寻找这个性质的边界，既可以寻找满足这个性质的边界，也可以寻找不满足这个性质的边界。
二分的写法：
1.确定mid值后，先写一个check函数。判断check 为 true or false后 如何更新区间。
2.对左边区间的二分：
找到独立的中间值：(l + r + 1)/2
判断中间值是否满足这个性质。
if ( check(mid) )

• true then l = mid (边界为 mid to r，要包含mid)

• false then r = mid - 1 (边界为 l to mid)
  3.对右边区间的二分：
  找到独立的中间值：( l + r )/2
  if ( check(mid) )

• true then l = mid (边界为 l to mid )

• false then r = mid + 1 (边界为 mid + 1 to r)

算法模板：
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;
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)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

• C + + 的整数取证是向下取整。