二分 以及例题

适用题型：

已经排序且需要高效查找特定元素

模板1（不加1）

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

模板2（加1）

while(l < r)
          {
            int mid = (l + r + 1) >> 1;
            if (a[mid] > k){
              r = mid - 1;
            }
            else l = mid;
          }

例题：

1227. 分巧克力 - AcWing题库

#include<iostream>
#include<cstring>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
/* 
1.切的块数随边长增大减小：k = (wi/x)*(hi/x)
2.二分条件： f[x] >= k
 */
const int N = 1e5+10;
typedef long long ll;
int n,k;
int h[N], w[N];

bool check(int x)
{
    int num = 0;
    for(int i = 0; i < n ; i ++ )
    {
        num += ( w[i]/x ) * ( h[i]/x );
        if(num >= k) return true;
    } 
    return false;
}

int main()
{
    IOS;
    cin >> n >> k;
    for(int i = 0; i < n; i ++ ) cin >> h[i] >> w[i] ;
    
    int l = 1, r = 1e5;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1; 
    }
    cout << l ;
    return 0;
}

730. 机器人跳跃问题 - AcWing题库

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

const int N = 1e5+10;
int n,h[N];

bool check(int e)
{
  for(int i = 1; i <= n; i ++)
  {
    e = e *2 - h[i];
    if(e >= 1e5) return true;
    if(e < 0) return false;
  }
  return true;
}
 
int main()
{
    IOS;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];

    int l = 0, r = 1e5;
    while(l < r)
    {
      int mid = l + r >> 1;
      if(check(mid)) r = mid;
      else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}