二分

· · 个人记录

二分

二分查找

例题 1：递增序列二分查找

洛谷T164755整数查找

模型：根据大小关系可将序列分为三个部分：a_i < x, a_i = x, a_i > x，这三个部分可以看作为-1, 0, 1的三段。


int Find(long long x){
  int l = 1, r = n;
  while (l <= r){
    int mid = (l + r) >> 1;
    if (a[mid] == x){
      return mid;
    }
    else if (a[mid] < x){
      l = mid + 1;
    }
    else{
      r = mid - 1;
    }
  }
  return 0;
}

例题 2：非减序列二分查找

洛谷 T164761 整数插入

模型：在非减序列中查找 ≥x 的数的第一次出现位置，可以将序列看作为 0, 1 的两段，相当于查找分界线。


int Find(long long x){
  int l = 1, r = n + 1; // r = n + 1 为边界条件
  while (l < r){
    int mid = (l + r) >> 1;
    if (a[mid] >= x){
      r = mid;  // mid 可能成为答案，因此不减 1
    }
    else{
      l = mid + 1; // mid 不可能为答案，因此加 1
    }
  }
  return l;
}

几种模型：

二分答案

原问题可以找到一个单调函数，答案可以分为使原问题有解（1）和无解（0）的两段，那么相当于查找分界线。

本质仍是二分查找并判断问题是否有解。

例题 1：整数域上的二分答案

洛谷 P1182 数列分段 Section II

思路：当每段和的最大值 x 越大，数列能够分成的最少段数 f(x)f(x) 越小，求使 f(x)<m 的最小整数 x。

模型：随着 x 的增大，原问题有解情况为 0-1 分段，查找 1≥1 的最小整数 x。


// 合法性检查
bool check(int x){
  long long sum = 0;
  int cnt = 1;
  for (int i = 1; i <= n; i++){
    if (sum + a[i] <= x){
      sum += a[i];
    }
    else{
      sum = a[i];
      cnt++;
    }
  }
  return cnt <= m;
}

// 二分答案
int Find(){
  int l = *max_element(a + 1, a + n + 1), r = INF;
  while (l < r){
    int mid = (l + r) >> 1;
    if (check(mid)){
      r = mid;
    }
    else{
      l = mid + 1;
    }
  }
  return l;
}

例题 2：实数域上的二分答案

二分的答案从整数域变为实数域，需要考虑精度问题。精度一般设置为 10^{-x-2} ，其中 x 为题目要求的精度。

洛谷 P1163 银行贷款

提示：当利率为 x ，每月分期金额为 A，偿还贷款 M 月时，P = \sum\limits^{M}_{i=1}A * ( \frac{1}{1 + x} )^i


bool Check(double x){
  double t = 1, ans = 0;
  for (int i = 1; i <= m; i++){
    t *= 1 / (1 + x);
    ans += a * t;
  }
  return ans <= p;
}

double Find(){
  double l = 0, r = 5;
  while (r - l > eps){
    double mid = (l + r) / 2;
    if (Check(mid)){
      r = mid;
    }
    else{
      l = mid;
    }
  }
  return l;
}