前言

按照以往慣例，今天不是 20251020 - 二分 & 分治嗎？

二分

使用二分的原因

在有序數組或有單調性的題目中，可以使用二分查找/二分答案來優化枚舉。

原理

每次指定一個區間，把他劈成兩半，排除不合法的區域，重復執行直到得到答案。

寫法：

方法零：

int erfen(int x){
    int pos = lower_bound(a.begin(),a.end(),x)-a.begin();
    return a[pos] == x ? pos : -1;
}

方法一：

int erfen(int x){
    int l = Left_Interval - 1,r = Right_Interval + 1;
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        if(check(...)){
            l = mid;
        }else{
            r = mid;
        }
    }
    return a[r] == x ? pos : -1;
}

方法二：

int erfen(int x){
    int l = Left_Interval,r = Right_Interval,ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(...)){
            l = mid + 1;
            ans = mid
        }else{
            r = mid - 1;
            // ans = mid
        }
    }
    return a[ans] == x ? pos : -1;
}

方法三（不正經MZC）：

int erfen(int x){
    int l = Left_Interval - 1,r = Right_Interval;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(check(...)){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    return a[...] == x ? pos : -1;
}

二分答案

再有單調性的題目中，可以通過二分答案，把時間復雜度從 \(O(...n)\) 優化到 \(O(...log_2n)\)。

對于 \(n = 10^5\) 時，二分答案很有用！

例題：[跳石頭](20251020 - 二分 - Virtual Judge)

想法一：暴力

枚舉每一個最長間隔，在貪心判斷是否可行！

想法二：二分答案

可以發現，當間隔越長，可以放的石頭就越少，所以考慮二分答案！

void solve(){
  scanf("%d%d%d",&l,&n,&m);
  for(int i = 1;i <= n;i++)
    scanf("%d",&a[i]);
  a[++n] = l; // 至于為什么？T_T，最后一個石頭跳到終點也可能跳不到，可惜了罰時了！
  int l = -1,r = 1e9 + 1;
  while(l + 1 < r){
    int mid = (l + r) / 2;
    if(check(mid))  
      l = mid;
    else
      r = mid;
  }
  printf("%d\n",l);
}