二分查找+二分答案

### 二分查找 二分查找：在一个已知的有序数列上进行二分地查找 ``` while(l<r){ int mid=(l+r)/2; if(a[mid]==x) { ans=mid; break; } if(a[mid]>x) r=mid; else l=mid+1; } ↓------最小值早出现------↓ while(l<r){ int mid=(l+r)/2; if(a[mid]>=x) r=mid; else l=mid+1; } cout<< l; ↓------最大值晚出现------↓ while(l<r){ int mid=(l+r+1)/2; if(a[mid]<=x) l=mid; else r=mid-1; } cout<< r; ``` ### 二分答案 二分答案：很多答案都满足题目要求，答案有一个区间，在这个区间中二分，直到找到最优答案（最大、最小） 1. 答案在一个区间内（一般情况下，区间会很大，暴力超时） 2. 很容易判断一个答案可行不可行 3. 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。 ``` ↓------最小值早出现------↓ while(l<r) { int mid=(l+r)/2; if(check( )) r=mid; else l=mid+1; } cout<< l; ↓------最大值晚出现------↓ while（l<r） { int mid=(l+r+1)/2; if(check( )) l=mid; else r=mid-1; } cout<< r; ``` 其实在STL里面也有已经实现好的二分函数，包含于algorithm库中。 • lower_bound(begin,end,val)：在**有序数组** [begin,end) 中找到第一个**大于等于** val 的值并返回其地址。 • lower_bound( begin , end , val , **less**<type>() )：加入了 **less<type>() 自定义比较函数**：适用于**从小到大**排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找**第一个大于等于val**的数字 • lower_bound( begin , end , val , **greater**<type>() )：加入了 **greater<type>()** 自定义比较函数：适用于**从大到小**排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找**第一个小于等于val** 的数字 • upper_bound(begin,end,val)：在**有序数组**[begin,end)中找到第一个**大于** val 的值并返回其地址。 • upper_bound( begin , end , val , **less**<type>() ) AI写代码 上述代码中加入了 less<type>() 自定义比较函数：适用于**从小到大**排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找**第一个 大于 val** 的数字 • upper_bound( begin , end , val , **greater**<type>() ) 上述代码中加入了 greater<type>() 自定义比较函数：适用于**从大到小**排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找**第一个 小于 val** 的数字 和大多数 STL 函数一样，begin 指数组首地址，end 指末地址+1。需要注意的是，如果在数组中返回得到的结果将会是一个地址，而我们经常需要将其转化为下标。 例如下面的代码得到的就是 a 数组（下标从0开始）第一个大于等于 val 的值的下标。 ``` int pos = lower_bound(a, a+n, val) - a; ``` #### 二分好题 AT_abc203_d,二分+前缀和 AT_abc144_e, AT_abc119_d, AT_abc205_d