你真的懂二分吗？

二分简述：

二分算法，又称为二分搜索或折半搜索，是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两半，然后根据目标值与中间元素的大小关系来决定是继续在左侧还是右侧进行搜索。这个过程会不断重复，直到找到目标值或搜索范围为空为止。

下面是二分算法的一般步骤：

1. 初始化：设置两个指针，一个指向数组的起始位置（low），另一个指向数组的结束位置（high）。此时，low = 0，high = 数组长度 - 1或者low = 1，high = 数组长度 。

2. 循环条件：只要low小于等于high，就继续循环。

3. 计算中间位置：在每次循环中，计算中间位置mid=(low + high) / 2。

4. 比较：比较中间元素与目标值。

  - 如果中间元素等于目标值，搜索成功，返回mid。

  - 如果中间元素大于目标值，说明目标值在数组的左侧，更新high为mid - 1。

  - 如果中间元素小于目标值，说明目标值在数组的右侧，更新low为mid + 1。

5. 循环结束：如果low大于high，说明没有找到目标值，搜索失败。

二分算法的时间复杂度是O(log n)，其中n是数组的长度。这使得它在大规模数据搜索中非常高效。然而，二分搜索的一个前提条件是数组必须是有序的。

二分算法不仅可以用于搜索，还可以用于解决一些优化问题，如找到函数的最大值或最小值等。

二分模板：

在写这篇博客之前看了很多博主的模板，我认为二分的模板只有两种，所有的题都逃不过这两种模板。做过的题为例，100%都属于这两种模板，不是的话，你来找我！

首先贴一个我刚开始学二分时候初步了解，是不完全正确的，但是是最容易理解的一种。

不完全正确的二分：

int quick(int a[],int l,int r,int x){
  int mid;
  while(l<=r){
    mid=(l+r)/2;
    if(x==a[mid]){
      break;
    }else if(x>a[mid]){
      l=mid+1;
    }else if(x<a[mid]){
      r=mid-1;
    }
  }
  return mid;
}

上面这一种可以查找只有唯一一种数的情况，类似1，3，4，5... 这样只有唯一一个的数。像1，1，2，2，2... 这种如果想找到最小的数且靠右边的数，以上模板可能比较难实现。一般题目中都是不是唯一数的情况。这就是我们以下两种模板中的一个。

模板一（查找最右边的）：

数组==[1,1,1,1,2,2,2,3...]，想要查找最右边的1，就是第四个1，如果用上面的模板，它查到一个1就立马返回了，不管你是哪一个1，取决于你的左右边界了。这样很难实现，那么我们就有下面这一个模板，先来看板子。

while(l<r){
  int mid=l+r+1>>1;
  if(check(mid)){//如果条件成立
    l=mid;
  }else{
    r=mid-1;
  }
}
return l;

初始l=0，r=len-1。首先判断到任意一个1无论在什么位置，比如说在第二个1，那么check(mid)条件是成立的，我就更新左端点把范围给到右区间，让他去找最右边的1，不断去找... 当判断到最后一个1时，再更新l==r了，此时就退出循环了，也就找到答案了。

模板二（查找最左边的）：

还是上面这个数组==[1,1,1,1,2,2,2,3...]，如果要查找最左边的一个2，就是第一个2。就可以用下面这个模板。

while(l<r){
  int mid=l+r>>1;
  if(check(mid)){
    r=mid;
  }else{
    l=mid+1;
  }
}
return l;

初始l=0，r=len-1。首先判断到任意一个2无论在什么位置，比如说在第三个2，那么check(mid)条件是成立的，我就更新右端点把范围给到左区间，让他去找最左边的2，不断去找... 当判断到第一个2时，再更新l==r了，此时就退出循环了，也就找到答案了。

二分底层实现：

在在做题中，二分板子自然很好用，但是还需要写很多代码，以下在特殊情况下可以用upper_bound与lower_bound来代替，这两个函数的底层都是用二分实现的，时间复杂度同样是O(log n)，都包含在头文件#include<algorithm>中。

upper_bound:

upper_bound函数是C++ STL中的一个函数，用于在有序序列中查找一个给定的值，并返回第一个大于该值的位置迭代器。

函数原型如下：

upper_bound( first, last, const T& value );

其中，first和last是指定序列的起始和结束迭代器，value是要查找的值。

upper_bound函数会首先在[first, last)区间内进行二分查找，找到第一个大于value的位置，并返回一个指向该位置的迭代器。如果所有元素都小于等于value，则返回last迭代器。

注意，该函数要求序列是有序的，否则结果是未定义的。另外，upper_bound函数使用的是半开区间表示法，即[first, last)表示包含first，但不包含last。

以下是一个使用upper_bound函数查找有序序列中大于某个值的示例：

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    vector<int> v = {1, 2, 3, 4, 4, 5, 6, 6, 7, 8};
    int value = 4;
    auto it = upper_bound(v.begin(), v.end(), value);
    if (it != v.end()) {
        cout << "First element greater than " << value << " found at position " << distance(v.begin(), it) << endl;
    } else {
        cout << "No element greater than " << value << " found" << endl;
    }
    
    return 0;
}

输出结果为：

First element greater than 4 found at position 5

这个例子中，有序序列v中第一个大于4的元素是5，upper_bound函数返回的迭代器指向5的位置。

lower_bound:

lower_bound函数是C++ STL中的一个函数，用于在有序序列中查找一个给定的值，并返回第一个大于等于该值的位置迭代器。

函数原型如下：

lower_bound( first, last, const T& value );

其中，first和last是指定序列的起始和结束迭代器，value是要查找的值。

lower_bound函数会首先在[first, last)区间内进行二分查找，找到第一个大于等于value的位置，并返回一个指向该位置的迭代器。如果所有元素都小于value，则返回last迭代器。

注意，该函数要求序列是有序的，否则结果是未定义的。另外，lower_bound函数使用的是半开区间表示法，即[first, last)表示包含first，但不包含last。

以下是一个使用lower_bound函数查找有序序列中大于等于某个值的示例：

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    vector<int> v = {1, 2, 3, 4, 4, 5, 6, 6, 7, 8};
    int value = 4;
    
    auto it = lower_bound(v.begin(), v.end(), value);
    if (it != v.end()) {
        cout << "First element greater than or equal to " << value << " found at position " << distance(v.begin(), it) << endl;
    } else {
        cout << "No element greater than or equal to " << value << " found" << endl;
    }
    
    return 0;
}

输出结果为：

First element greater than or equal to 4 found at position 3

这个例子中，有序序列v中第一个大于等于4的元素是4，lower_bound函数返回的迭代器指向4的位置。

题目实践：

洛谷二分题单：

AcWing题目：

蓝桥杯：

由于文章长度，只在此篇博客写几个具有代表性的题。

AcWing 1227. 分巧克力

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足：

1. 形状是正方形，边长是整数
2. 大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式

第一行包含两个整数 N和 K。

以下 N行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

数据范围

1≤N,K≤10^5,

1≤Hi,Wi≤10^5

输入样例：

2 10
6 5
5 6

输出样例：

2

AC代码：

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,k;
int h[N],w[N];
int maxx;
bool check(int x){
  int sum=0;
  for(int i=0;i<n;i++){
    int l=h[i]/x;
    int r=w[i]/x;
    sum+=l*r;
  }
  return sum>=k?true:false;
}
int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>h[i]>>w[i];
    maxx=max(maxx,max(h[i],w[i]));
  }
    //尽可能大，所以第一个模板，因为此题答案唯一，也可以用最初的那个模板
  int l=1,r=maxx;
  while(l<r){
    int mid=l+r+1>>1;
    if(check(mid))l=mid;
    else r=mid-1;
  }
  cout<<l<<endl;
  return 0;
}

洛谷 P2678 [NOIP2015 提高组] 跳石头

AC代码：

#include<iostream>
using namespace std;
const int N=5e4+5;
int num,n,m;
int a[N];
bool check(int x){
  int sum=0,now=0;//sum需要搬走的数量，now上一个相对石块位置
  for(int i=1;i<=n+1;i++){
    if(a[i]-now<x)sum++;//石块距离小于理想的距离，这个石头需要搬
    else now=a[i];//更新对比的石块
  }
  return sum>m?false:true;
}
int main(){
  cin>>num>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  a[n+1]=num;//多加一个终点
    //求最大最短跳跃距离的最大值，第一个模板
  int l=0,r=num;
  while(l<r){
    int mid=l+r+1>>1;
    if(check(mid))l=mid;
    else r=mid-1;
  }
  cout<<l<<endl;
  return 0;
}