高级二分查找

发表于 更新于 分类于

高级二分查找

知识回顾

  • 给定一个单调不下降的序列a[1..n]，问x是否在其中。

  • 根据初始信息，答案显然位于[1,n]。

  • 假设我们已知答案位于[l,r]。

  • 若l>r，则说明x不在其中。

  • 否则取mid=(l+r)/2，比较x与a[mid]的大小关系。

  • 若x==a[mid]，则x在其中。

  • 若x<a[mid]，则答案位于[l,mid-1]。

  • 若x>a[mid]，则答案位于[mid+1,r]。 ### 二分的适用范围

  • 当x<a[mid]时，可以把可能区间缩小至[1,mid-1]是因为a[mid]<=a[mid..n]。

  • 二分的适用范围：单调不下降/不上升的序列或函数。

代码实现

bool find(int n, int a[], int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (x == a[mid]) return true;
        if (x < a[mid]) r = mid - 1;
        else l = mid + 1;
    }
    return false;
}

例子：找平方根下取整

ll findsq(ll val){
    ll l = 0;
    ll ans=-1; 
    ll r = maxmid;
    while(l <= r ){
        ll mid = (l + r) >> 1;
        if((mid*mid)<=val){
            ans=mid;
            l = mid +1;
        }
        else{
            r = mid -1;
        }
    }
    return ans;
}

例题1-序列划分

  • 给定n个正整数a[1..n]，将这个序列从左到右划分成m段，使得每段至少有一个数。
  • 你需要让数字之和最大的那一段的数字和尽可能得小。
  • 1 <= m <= n <= 100000。
  • 1 <= a[i] <= 10^9。

代码

贪心

int f(long long x) {
    long long sum = 0;//当前段的数字之和
    int cnt = 1;//最少切出的段数
    for(int i = 1; i <= n; i++) {
        if (a[i] > x) return -1;//无解
        if (sum + a[i] <= x) sum += a[i];
        else sum = a[i], cnt ++;
    }
    return cnt;
}

二分解法（更快

  • 若f(x)有解，则若能划分成f(x)段，必然能划分成f(x)+1段。
  • 另一方面，若f(x)有解，则f(x)≥f(x+1)，因为x+1的限制变松了。
  • 显然我们要求的答案位于[max(a[1..n]), sum(a[1..n])]之中。
  • 我们需要在这个范围里，找到最小的x，使得f(x)≤m。
  • 因为f(x)≥f(x+1)，是单调函数，二分即可。

需要通过O（n）算法f处理数据，看是否满足 二分即可（可以使用ANS储存中间值，更方便）

long long solve(long long mx, long long sum) {
    long long l = mx, r = sum, ans = r;
    while (l <= r) {
        long long mid = (l + r) / 2;
        int tmp = f(mid);
        if (tmp <= m) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

最大/最小 等问题可以用二分解决

例题2 - Tower

例2-Ice Cream Tower

  • 给定n个正整数a[1..n]和一个正整数k。
  • 一座高度为k的塔b[1..k]满足b[1]*2≤b[2]，b[2]*2≤b[3]，b[3]*2≤b[4]…
  • 你要从中选择一些数来叠很多座高度为k的塔，问最多能叠多少座塔。
  • 2 ≤ n ≤ 100000。
  • 2 ≤ k ≤ 30。
  • 1 ≤ a[i] ≤ 10⁹。

考虑的问题

  • 如何判断能否叠出x座塔？
  • 将序列从小到大排序，那么最优情况下前x小的数字将作为这x座塔的底层。
  • 从小到大依次考虑剩下的数，不断尝试铺出第二层、第三层…第k层。
  • 如果一个数铺不上去，那么舍弃就好。
  • 考虑完所有数字之后，判断每座塔的高度是否达到k即可。

代码：

using namespace std;
typedef long long ll;
const int N=300010;
int Case,cas,n,k,i,l,r,mid,ans,c[N]; ll a[N],b[N];
bool check(int x){
    int i,j;
    for(i=1;i<=x;i++)b[i]=a[i],c[i]=1;
    for(i=x+1,j=1;i<=n;i++)if(a[i]>=b[j]*2){
        b[j]=a[i];
        c[j]++;
        j++;
        if(j>x)j=1;
    }
    for(i=1;i<=x;i++)if(c[i]<k)return 0;
    return 1;
}
int main(){
    scanf("%d",&Case);
    for(cas=1;cas<=Case;cas++){
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        l=1,r=n,ans=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid))l=(ans=mid)+1;else r=mid-1;
        }
        printf("%d\n",ans);
    }
}

例题3 - K小

  • 给定n个正整数a[1..n]和m个正整数b[1..m]。
  • 在n*m个a[i] + b[j]中，找到第k小的数（不去重）。
  • 1 ≤ n,m ≤ 100000。
  • 1 ≤ k ≤ n * m。
  • 1 ≤ a[i], b[i] ≤ 10^8。

思路：

例3-第K小的数

  • 本题的单调函数是什么呢？
  • 设f(x)表示有多少对i,j满足a[i]+b[j]<=x。
  • 则f(x)<=f(x + 1)，是单调函数。
  • 我们需要找到最小的x，满足f(x)>=k。
  • 二分。
  • 给定x，如何统计有多少对i,j满足a[i]+b[j]<=x？
  • 将a和b都从小到大排序后双指针统计。

代码

long long f(int x) {
    long long cnt = 0;
    int j = m;
    for (int i = 1 ; i <= n ; i ++) {
        while (j && a[i] + b[j] > x) j --;
        cnt += j;
    }
    return cnt;
}

j 直接减小即可，因为a序列有序，j只能减小，O（n）