二分用法总结（一）

二分是一个加速搜索的工具，对于有序的内容,可以通过二分来改善遍历的低效率,而有序的内容不限定是数字,可以是任何有序的.

二分最常见的解法思路步骤是

  1. 转化题意
  2. 发掘其中有序的部分
  3. 建立顺序标识运算函数f
  4. 二分查找有序部分
  5. 输出结果

在更复杂的竞赛中,二分只会是整个题目的一小部分,常见的工具有lower_bound/upper_bound,常见的复杂题目的配合算法和解题手段有预处理,二分答案

另外注意到数值类的二分,注意溢出,对于可能溢出的解决方案

一个是使用更大的数据类型如long long

另一个是判断符号,需要的时候使用l+(l-r)/2来代替(l+r)/2

技巧

  1. 数值类,字符类,pair<>类可比较用lower_bound直接查找,获取查找结果的下标
lower_bound(arr.begin(),arr.end(),val) - arr.begin();
  1. 每个状态有自己的函数,且上下界一个满足一个不满足, 在二分过程中,保持这两个界所对应的满足关系
while(l+1 < r){ // 始终不会相等
    auto m = (l+r)/2;
    if(f(m,target)){ // 比较函数 满足
        r = m;
    }else{ // 不满足
        l = m;
    }
}
return l;
  1. 每个状态有自己的函数,且上界满足,下届未知,对于未知的,最终要让它变为满足
while(l < r){ // 会相等
    auto m = (l+r)/2;
    if(f(m,target)){ // 比较函数 满足
        r = m;
    }else{ // 不满足
        l = m + 1;
    }
}
return l;

练手题目

题目1

求平方根（二分）

这道题可以用技巧2, 明确能找到满足和不满足的上下界二分, 运算比较函数如下

bool f(int m,int x) {
	return m*m > x;
}

alt

题目2

二分查找（二分）

这道题可以用技巧1, 或技巧3, 直接用lower_bound或者手写上下界查找, 运算比较函数如下

bool f(int m,int v){
	return a[m] < v;
}

alt

题目3

在转动过的有序数组中寻找目标值(二分)

这道题可以用技巧1, 通过分治得到的局部的子数组,再对子数组直接求下标, 对于有偏移量的查询, 用偏移量的指针替代.begin(),.end()即可

int idx = lower_bound(A+l,A+r+1,target) - A;

alt

题目4

矩阵元素查找（二分）

这道题可以使用技巧1, 先通过分治把二维数组降低到一维, 再用二分找下标

int idx = lower_bound(A.begin(),A.end(),target) - A;

alt

题目5

二分查找-II（二分）

这道题可以使用技巧1, 和上面题目2是同样的,唯一区别是这个要找恰好相当,而上面找大于等于,只是输出时不同,查找是相同的,运算比较函数也是

bool f(int m,int v){
	return a[m] < v;
}

alt