二分

二分查找元素

原理

二分使用的条件是有单调性，比如有序的序列，事实上二分是分治算法思想。本质是将问题抽象化为找一个分界面，分界面左边不满足某一性质，而右边满足某一个性质。这时候左边边界缩减时需要多缩减一个，因为左边不满足性质；右边边界缩减到当前mid，不用多缩减。下边代码的check函数即是满足某种性质的判断函数，当满足性质时返回 true, 不满足时返回false。

当搜素结束时，左右边界重合，即l == r。如果有l = mid的情况，需要l + r + 1 >> 1才能够避免最后两个数相邻时，mid永远更新为左边界的死循环。

二分查找分为整数二分和浮点数二分，浮点数查找时原理相同，但是要求精度小于一定数时停止。浮点数二分比整数二分容易很多，不需要考虑很多边界条件的情况。

模板

//每次右边界缩减为mid的情况
while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}
//每次左边界缩减为mid的情况
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid + 1;
}

//例子：求一个有序序列中的左右边界
//1 【2 2 2】 3 3 
//   ↑    ↑
//   ①    ②
while (l < r)
{
    int mid = l + r >> 1;
    if (a[mid] >= x) r = mid;
    else l = mid + 1;
}
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (a[mid] <= x) l = mid;
    else r = mid - 1;
}

//浮点数二分
const double eps = 1e-8;

while (r - l > eps)
{
    int mid = l + r / 2.0;
    if (check(mid)) l = mid;
    else r = mid;
}

例题

构造单调性+二分查找，重点在于单调性的构造

LC.剑指offer11.旋转数组的最小数字（简单）

有趣的二分，如何解决有重复数字无法确定左右边界收缩的情况

二分搜索答案

原理

答案很多时候是有范围的，当某一个问题验证某一个答案的时间复杂度乘以二分区间范围的log时，可以考虑搜索答案。通过不断的尝试排除错误答案，且是以指数速度排除，最终得到正确答案。这里一般在验证答案的时候，可以采用某种程度的贪心策略，并且将原问题中单调性质进行转化，能够通过一次的验证缩小答案范围。

这类题往往不是简单的搜索答案，而是将问题某种程度的转化之后，再搜索答案。