图文并茂带你入门二分查找算法

原理

二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

为了方便理解，我们以数组1, 2, 4, 5, 6, 7, 9, 12, 15, 19, 23, 26, 29, 34, 39，在数组中查找26为例，制作了一张查找过程图，其中low标示左下标，high标示右下标，mid标示中间值下标

二分查找的过程就像上图一样，如果中间值大于查找值，则往数组的左边继续查找，如果小于查找值这往右边继续查找。二分查找的思想虽然非常简单，但是查找速度非常长，二分查找的时间复杂度为O(logn)。虽然二分查找的时间复杂度为O(logn)但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值，比例O(1000)。我们来看一张二分查找与遍历查找的效率对比图。

❝ 图片来源网络
❞

从图中可以看出二分查找用了三步就找到了查找值，而遍历则用了11步才找到查找值，二分查找的效率非常高。但是二分查找的局限性非常大。那二分查找有哪些局限性呢？

局限性

二分查找依赖数组结构

二分查找需要利用下标随机访问元素，如果我们想使用链表等其他数据结构则无法实现二分查找。

二分查找针对的是有序数据

二分查找需要的数据必须是有序的。如果数据没有序，我们需要先排序，排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。

但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。

所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用

数据量太小不适合二分查找

如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多，只有数据量比较大的时候，二分查找的优势才会比较明显。

数据量太大不适合二分查找

二分查找底层依赖的是数组，数组需要的是一段连续的存储空间，所以我们的数据比较大时，比如1GB，这时候可能不太适合使用二分查找，因为我们的内存都是离散的，可能电脑没有这么多的内存。

代码实现

二分查找可以使用循环或者递归来实现，我们来看看两种实现方式的代码。

循环

/**
     * 循环版二分查找
     *
     * @param nums  数组
     * @param n     数组长度
     * @param value 要查找的值
     * @return
     */
    private static int bserach(int[] nums, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            // 找出中间下标 
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                high = mid - 1;
            } else if (nums[mid] < value) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

递归

/**
     * 递归算法实现二分查找
     *
     * @param nums  数组
     * @param low   左下标
     * @param high  右下标
     * @param value 要查找的值
     * @return
     */
    private static int recursiveBserach(int[] nums, int low, int high, int value) {

        if (low > high) return -1;

        // 找出中间下标
        int mid = low + ((high - low) >> 1);

        if (nums[mid] == value) {
            return mid;

        } else if (nums[mid] > value) {
            return recursiveBserach(nums, low, mid - 1, value);
        } else {
            return recursiveBserach(nums, mid + 1, high, value);
        }
    }

二分查找的代码实现起来比较简单，需要说明的地方是中间值的计算，中间值得计算有两种方式，方式一：int mid = (low +high)>>1，方式二：int mid = low + ((high - low) >> 1)。方式一存在溢出的风险，当low和high比较大时，有可能会导致mid的值错误，从而使程序出错。方式二则可以保证生成的mid一定大于low，小于high。

上面的二分查找比较简单，我们来看看变形的二分查找。

查找第一个等于给定值的元素

比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9，我们需要查找第一个等于4的元素。

    /**
     * 查找第一个等于给定值的元素
     *
     * @param nums
     * @param length
     * @param value
     * @return
     */
    private static int bsearchFirstValue(int[] nums, int length, int value) {
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                high = mid - 1;
            } else if (nums[mid] < value) {
                low = mid + 1;
            } else {
                // 判断当前是第一个元素或者前一个元素不等于要查找的值，则返回下标，如果前一个元素也等于要查找的值，则继续往前查找。
                if ((mid == 0) || (nums[mid - 1] != value)) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }

其他的都差不多，主要的区别是在nums[mid]==value时候，因为我们要查找的是第一个等于给定值的元素，所以我们需要判断mid的前一个元素等不等于给定值，如果前一个元素也等于给定值，则需要继续往左边查找。

查找第一个大于给定值的元素

比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9，15,26,34，45，我们随便输入一个值，这个值可以是数组里面的值，也不可不在数组里面，查找出第一个比给定值大的元素。

/**
     * 查找第一个大于给定值的元素
     *
     * @param nums   数组
     * @param length 数组的长度
     * @param value  给定的值
     * @return
     */
    private static int bserachFirstOverVlaue(int[] nums, int length, int value) {
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                // 判断当前是第一个元素或者前一个元素小于等于给定值，则返回下标，如果前一个元素大于给定的值，则继续往前查找。
                if ((mid == 0) || nums[mid - 1] <= value) return mid;
                else high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

我们需要判断当nums[mid] > value时，nums[mid-1]是否小于或者等于给定值，如果是则mid就是第一个大于给定值的元素，如果不是这继续往左边查找。

     low = mid + 1;
        }
    }
    return -1;
}

我们需要判断当`nums[mid] > value`时，`nums[mid-1]`是否小于或者等于给定值，如果是则`mid`就是第一个大于给定值的元素，如果不是这继续往左边查找。

以上就是关于二分查找的相关知识，二分查找虽然性能比较优秀，但应用场景也比较有限，底层必须依赖数组，并且还要求数据是有序的。所以我们在选用算法时需要从多方面考虑。

很多人对二分感到很苦恼，很困惑，可能是因为二分的边界很难掌握，也许是判断条件难写…

然而，很幸运，你找到了这篇文章，仔细看下去，这篇文章将带你学透二分！！！

二分可以简单分为二分查找与二分答案。

可能你听说过二分查找，二分查找和二分答案是不是一回事呢？答案是否定的。二分查找只是单纯的查找就可以了，简单的控制好边界条件。而二分答案也许稍复杂些。

首先，我们看一下二分的模板：

模板1：

	while (l < r)
    {
        int mid = l + r >> 1;	//(l+r)/2
        if (check(mid))  r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }

模板2：

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

看到这，以后的你就不会因为边界问题而困惑了！！！

第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。

只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一；
只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一；

二分套这两个模板，肯定没错！（只要判断条件写对）亲测有效！！！
下面的题目更能证明这句话！

这两个模板一定要牢牢记住哦

当然，二分可能在实数中进行，那自然少不了浮点二分。

模板3：（浮点二分）

	while(r-l>1e-5) //需要一个精度保证
	{
		double mid = (l+r)/2;
		if(check(mid)) l=mid; //或r=mid;
		else r=mid; //或l=mid;
	}

浮点二分就相对简单多了，因为浮点除法不会取整，所以mid，l，r，都不用加1或减1.

我们先来学二分查找：

二分查找也称折半查找，顾名思义，就是每次查找去掉不符合条件的一半区间，直到找到答案（整数二分）或者和答案十分接近（浮点二分）。

光说不练假把式，来个例题：

例题1——查找

分析：这题就是典型的二分查找入门题。

首先，区间是有单调性的，查找第一次出现的位置，如果查到一个值比目标值大，就把右半边放弃，因为右半边肯定也比目标值大；同样，如果查到值比目标值小，那就放弃左半边。

本文的所有例题都有分析，题解，并注上详细注释。先自己尝试一下，再看题解哦。

code：

#include<iostream>
using namespace std;

const int N=1000010;
int a[N],x,q,n;

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	while(q--)
	{
		cin>>x;
		int l=1,r=n; //左右边界 
		while(l<r) //因为是找第一次出现的位置，那就是尽量往左来，就用模板1 
		{
			int mid=l+r>>1;
			if(a[mid]>=x) r=mid; //判断条件，如果值大于等于目标值，说明在目标值右边，尽量往左来
			else l=mid+1;
		}
		if(a[l]!=x){ //如果找不到这个值 
			cout<<-1<<" ";
			continue;
		}
		cout<<l<<" ";
	}
	return 0;
} 

有一个小问题就是，如果找不到这个值（即，集合里没有这个数）怎么办？因为判断条件是大于等于目标值，那返回的就是第一个大于目标值的位置。

好了，现在的你已经进入了二分世界的大门，此时让我们畅游吧！

例2——A-B 数对

分析：给出了C，我们要找出A和B。我们可以遍历数组，即让每一个值先变成B，然后二分找对应的A首次出现位置，看是否能找到。

如果找到A，那就二分找最后出现的位置，继而，求出A的个数，即数对的个数。

code：

#include<bits/stdc++.h>
using namespace std;

const int N=200010;
long long a[N],n,c,cnt,st;

int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);	//先排序 
	
	for(int i=1;i<n;i++)	//遍历每一个B 
	{
		int l=i+1,r=n;	//寻找A第一次出现的位置，使得A-B=C 
		while(l<r) //因为是第一次出现，尽量往左，模板1
		{
			int mid=l+r>>1;
			if(a[mid]-a[i]>=c) r=mid;	//判断：在目标值的右边，满足，往左来
			else l=mid+1;
		}
		if(a[l]-a[i]==c) st=l; //能找到C就继续 
		else continue;
		
		l=st-1,r=n;	//查找A最后出现的位置 
		while(l<r) //因为是最后一次出现，尽量往右，模板2
		{
			int mid=l+r+1>>1;
			if(a[mid]<=a[st]) l=mid; //判断：在目标值的左边，满足，往右去
			else r=mid-1;
		}
		cnt+=l-st+1;	//最后出现的位置减首次出现的位置就是区间长度，即A的个数 
	}
	cout<<cnt;
	return 0;
} 

如果你把上面的两个题完全搞懂了，那很容易就抽象出做题步骤：

如果题目明确说了 要求最小值（最前面的值）还是求最大值（最后面的值），就能判断是用模板1（求最小），还是用模板2（求最大）。
之后再根据模板1，或模板2，写出对应的判断条件；

但是，我们不建议死记模板，更重要的是在理解之后的灵活变通。比如，再看一个题。

例3——烦恼的高考志愿

分析：这题，就需要稍微理解一下下。

要求估分和分数线相差最小，那肯定分数线刚超过估分或者估分刚超过分数线。我们就转化为，求第一个大于等于估分的分数线的位置。

如此，这个位置的分数线或前一位置的分数线就是和估分相差最小的。

code：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
long long a[N],x,sum,n,m;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1); //排序勿忘 
	a[0]=-1e12;a[n+1]=1e12;	 //最后再解释
	
	while(m--)
	{
		cin>>x;
		int l=1,r=n+1;	//r设为n+1 
		while(l<r) //寻找第一个超过估分的学校，那它或它前面的一个学校就是目标学校 
		{
			int mid=l+r>>1;
			if(a[mid]>=x) r=mid;
			else l=mid+1;
		}
		if(a[l]-x<=x-a[l-1]) sum+=a[l]-x;
		else sum+=x-a[l-1];
	}
	
	cout<<sum;
	return 0;
	//a[0]=-1e12: 所有分数先可能都比估分大，那么l就为1，n-1就为0，故设a[0]为无穷小，则第一个值就为解 
	//a[n+1]=1e12: 所有分数线可能都比估分小，那么l就为n,a[l]-x可能为负，则设a[n+1]为无穷大，
				//并将r设为n+1，如此，l最大为n+1，则最后一个就为解 
}

此外，STL中还有两个二分函数：lower_bound 和 upper_bound；具体可以看这个博客；或这个（有很多大佬总结的知识点都很好，有啥不懂的话都可以翻博客）
有了这两个函数，我们就可以很方便的求出第一个大于（或等于）目标值的位置；于是，上面代码的中间可以这样改：

while(m--)
	{
		cin>>x;
		int t=lower_bound(a+1,a+n+1,x)-a; //如果分数线都比估分低，那返回的位置是n+1，否则返回第一个大于等于估分的位置。
		if(a[t]-x<=x-a[t-1]) sum+=a[t]-x;
		else sum+=x-a[t-1];
	}

是不是简洁多了？

最后，我们再来看一个浮点二分：

例4——银行贷款

分析：对于月利率，大几率是小数，那么，我们就需要浮点二分。

月利率的范围可以放大些，比如，0~500，然后从这个范围里查，直到和答案极度相近，终止。 最后的l或r，精确位数之后就是正确✔答案啦！

code：

#include<bits/stdc++.h>
using namespace std;

int sum,t,mon;
double sumt;

int check(double mid)
{
	sumt=sum;
	for(int i=1;i<=mon;i++){
		sumt=sumt+sumt*mid-t;
	}
	if(sumt > 0) return 1; 				//这里是>0, 感谢评论区小伙伴提醒~
	return 0;
} 

int main(){
	cin>>sum>>t>>mon;
	
	double l=0,r=500; //答案范围尽量开大些
	while(r-l>1e-5)	//精度保证 
	{
		double mid=(l+r)/2;
		if(check(mid)) r=mid;	//如果最后还不完了，说明利率高了 	
		else l=mid;
	}
	printf("%.1f",l*100);
	return 0;
} 

至此，相信你已经对二分查找有一个更加清晰的认识了。

课后再来几个练习题吧：
整数二分：
1、 数的范围
2、 砍树
实数二分：
3、 数的三次方根
4、 一元三次方程求解

学会了二分查找，来学二分答案！

首先:

二分查找与二分答案有何区别?

二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

其实，上面二分查找的例4，寻找的那个区间就是答案区间。

这不就相当于高中做选择题的时候，完了，不会做，那咋搞，把四个选项代进去看看对不对吧！哪个行得通那个就是答案！！

只不过我们现在要找的是最大的或者最小的答案。

如何判断一个题是不是用二分答案做的呢?

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）

2、直接搜索不好搜，但是容易判断一个答案可行不可行

3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。
1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid），对应模板1；
2、同样，求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid），对应模板2；

先看一个经典的二分答案入门：

例1——木材加工

分析：看，答案就在区间（1，100000000）里，就等着我们找呢，暴力肯定超时，那可能就用二分。

满足条件：

1，答案在一个区间里。
2，如果给一个答案，给目标一个小段的长度，很容易判断是否到K个了。
3，具有单调性，目标小段越长，那能切出的段数越少，目标小段越短，能切出的段数越多。而最终需要K个，从而很容易判断一个答案行不行。

一看求啥，求最长长度，最长？这不，关门打狗，模板2！ ！

那，判断条件？模板2，如果满足判断，l=mid。啥叫满足呢？那肯定是满足需要的段数了呗！

code：

#include<iostream>
using namespace std;

const int N=1e5+10;
long long a[N],n,m,sum,maxa;

int check(int mid)
{
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=a[i]/mid;
	}
	if(sum>=m) return 1; //总段数大于等于所需要的 
	return 0;
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i],sum+=a[i];
		if(a[i]>maxa) maxa=a[i];  
	}
	
	if(sum<m){cout<<0;return 0;} //先判断是否有解 
	
	int l=1,r=maxa;
	while(l<r) //模板2 
	{
		int mid=l+r+1>>1;
		if(check(mid)) l=mid; 
		else r=mid-1;
	}
	cout<<l;
	return 0;
}

是不是感觉很有意思？

再来看个经典的

例2——跳石头

分析：看题，这是啥？最短距离的最大值！这不就是二分答案的典型特征？还想啥，二分！

求最大？上模板2！！ 那，判断条件？

这时候就要注意了，我们二分的是最短距离，通过二分将这个最短距离（答案）最大化。那我们判断的时候肯定要保证mid是最短距离。

如何保证？我们要求抽过石头剩下的石头中，两个石头间的最短距离为mid，那就要保证剩下的任意两个间距都要大于等于mid。要保证这个，那就只能挑间距大于等于mid的石头跳，中间的石头都将会被抽走。

最后，计数可以被抽走的石头。如果可以被抽走的石头个数小于等于需要抽的M个了，就说明满足条件。因为：既然抽了小于M个都能满足剩下的石头中，两石头间的距离都大于等于mid了，那抽M个，更能满足！

有点晕？没关系！看了代码就懂了！

code：

#include<iostream>
using namespace std;

const int N=50010;
int a[N],n,len,m,mina=1e9+1,b[N];

int check(int mid)	//检查，是否最短距离为mid，如果两石头间距小于mid，不满足，移走 
{
	int cnt=0;
	int i=0,now=0;	//i表示目标位置，now为当前位置。
	while(i<n+1){
		i++;
		if(a[i]-a[now]<mid){ //两石头间距离小于mid，mid不是最短距离，不满足，移走该石头 
			cnt++;
		}
		else{	//符合，跳过去 
			now=i;
		}
	}
	if(cnt<=m) return 1;	//移走的石头个数小于 M，就能保证了任意两剩下的石头间距大于等于最短距离mid，那移走M个，更能保证 
	return 0;
}

int main(){
	cin>>len>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<mina) mina=a[i];
	}
	a[0]=0,a[n+1]=len; //首尾都有石头
	
	if(n==0){ //特判掉起点和终点之间没有石头的情况，可以想一下为什么。评论区中有答案。感谢 luojias 同学的hack数据！
		cout<<len; return 0;
	}

	//二分答案：检查每一个答案（最短距离mid）是否符合要求 
	long long l=1,r=1e10;
	while(l<r) //模板2
	{
		int mid=l+r+1>>1;
		if(check(mid)) l=mid; //要的是距离的最大，所以尽可能地往右走 
		else r=mid-1;
	}
	cout<<l;
	return 0;
} 

还没懂？没关系，我们再看一题！

例3——丢瓶盖

分析：距离最近的2个瓶盖距离最大？ 最短距离的最大值！ 二分！！

看——求最大值，模板二！

判断条件check：与上题不同的是，这题是保证拿走的那些瓶盖之间的最短距离最大（上题是保证剩下的石头最短距离最大，这两个容易混淆。是我没错了… ），那么，遍历的时候，只要满足这次和上次拿的那个瓶盖间距大于等于mid，就可以拿了。这样就保证了我们找的最短距离mid是最短的间距。

最后如果拿出的总瓶盖数大于等于目标值，就说明满足判断。因为：既然拿了超过目标值就能满足拿走的瓶盖间距大于等于mid，那拿目标值(B)个，肯定更能满足！

code：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;
int a[N],n,m,maxa;

//注意：这是拿出来的那些里，mid为最短距离，和跳石头不同的是，跳石头是在留下的里面，mid为最短距离 
int check(int mid)
{
	//now为最后一次拿的瓶盖位置，i为当前遍历的位置
	int i=1,now=1,cnt=0; 注意：第一个瓶盖必选，才能保证剩下的距离最大，从而挑出的瓶盖间最短距离最大化 
	while(i<n)
	{
		i++;
		if(a[i]-a[now]>=mid){ //保证拿走的瓶盖间距大于等于mid，才拿这个瓶盖，否则不能保证mid为最短距离
			now=i,cnt++;
		}
	}
	if(cnt+1>=m) return 1;	//如果拿出的总个数大于等于m，都能保证拿走的瓶盖间距大于等于mid，那拿出来m个，肯定也能满足！！
	return 0;

}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>maxa) maxa=a[i]; 
	}
	sort(a+1,a+n+1);
	
	int l=0,r=maxa;
	while(l<r) //模板2
	{
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	
}

做了上面两题，我们差不多又可以总结出规律了，心里是不是有点小激动？

最大值最小，最小值最大 类 问题解题方向：

最短距离最大化问题：保证任意区间距离要比最短距离mid大或相等（这样，mid才是最短距离）即：区间的距离>=mid

最长距离最小化问题：保证任意区间距离要比最大距离mid小或相等（这样，mid才是最大距离）即：区间的距离<=mid

哈哈哈，是不是太有趣啦？

快快，趁热打铁，再来！！

例4——数列分段 Section II

分析：没错，这次是最大值最小！
求最小值？ 哎对，模板1！
判断条件：要保证：每一段的和都小于等于最大值。也就是说，只要这一段的和加上下一个值大于最大值了，那下一个值加不得，得分段！接着段数++；
最后，统计出的总段数(cnt+1)小于等于目标值了，那就算满足；因为，既然分了小于目标值个段都能保证每段的和小于等于最大值，那么分目标值个段肯定还能保证！

还有一个小细节：l，和 r 的初始化。
所有段中的最大和肯定大于等于数列中的最大值（因为最大值最少单成一段，那所有段中的最大的和肯定要大于等于最大值），所以l要初始化为maxa。
同样，所有段中和的最大值，最大不过数列中的所有值的和。

code：

#include<iostream>
using namespace std;

const int N=100010;
typedef long long ll;
ll a[N],n,m,summ,mina=1e9+1,maxa;

int check(int mid)
{
	ll cnt=0,sum=0;
	for(int i=1;i<=n-1;i++)
	{
		sum+=a[i];
		if(sum+a[i+1]>mid) cnt++,sum=0; //不能满足 "区间间距小于最大距离"，那就分段 
	}
	if(cnt+1<=m) return 1;	//总的段数小于等于需要的段数，这样都能满足mid为每段的最大值，那么多分几段，肯定还能满足 
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i],summ+=a[i];	
		if(a[i]<mina) mina=a[i];
		if(a[i]>maxa) maxa=a[i];
	}
	
	int l=maxa,r=summ;	//l要设为maxa，所有段的最大值肯定大于等于maxa 
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid)) r=mid; //求的是最大值的最小，故尽量往左来 
		else l=mid+1;
	}
	cout<<l;
	return 0;
} 

好啦，至此，二分答案你就差不多掌握了。方法说的都是实打实的；
最后，在给出几道练习题吧：
1、进击的奶牛
2、路标设置
3、最佳牛围栏
4、kotori的设备

本文的课后练习题的答案在这个博客里。

相信看到这的你一定收获了不少吧。

讲的有点多，看不完的话可以先收藏。如果有没讲到的，后续会再更新。

有哪里不明白的话欢迎留言或评论，相互讨论，共同进步！

哪里写的有问题的话，还请大佬们不吝赐教。

参考博客：https://www.it610.com/article/1292865348768440320.htm

二分查找

写在前面：

（一）二分法的思想十分容易理解，但是二分法边界处理问题大多数人都是记忆模板，忘记模板后处理边界就一团乱（👁:“我懂了”， ✋ :"你懂个🔨"​）因为我此前也是记忆模板，所以现在想通过一边学习，一边将所学记录成博客教出去（费曼学习法），希望以后能自己推导出边界如何处理，而不仅仅是记忆模板。欢迎一起交流学习，如有看法不一样之处也欢迎留言一起讨论！

（二）我主要解释了二分法的左闭右闭区间，左闭右开区间两种写法，并且每个写法都举了相应的反例，范围写错的话可能会出现的错误等…

1. 简介

故事分享🏬：

有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。

保安怎么知道只有一本书📖没有登记出借，万一全部都没有登记呢​？

这个故事其实说出了二分查找需要的条件

• 用于查找的内容逻辑上来说是需要有序的
• 查找的数量只能是一个，而不是多个

比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。

在二分查找中，目标元素的查找区间的定义十分重要，不同的区间的定义写法不一样

因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：

• 左闭右闭[left, right]

• 左闭右开[left, right)

2. 例子

这是一个使用二分查找的例题

题目如下：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例一：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间。

出自704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)

二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。

• 首先选择数组中间的数字和需要查找的目标值比较
• 如果相等最好，就可以直接返回答案了
• 如果不相等
  • 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除
  • 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

二分法就是按照这种方式进行快速排除查找的

tips:

不用去纠结数组的长度是奇数或者偶数的时候，怎么取长度的一半，以下说明，可以跳过。

当数组的长度为奇数的时候：

是奇数的情况很简单，指向中间的数字很容易理解，如果需要查找的数字为29

因为29大于中间的数字大于11，所以左边的所有数字全部排除

当数组的长度为偶数的时候：

这个时候中间的数字两边的数字数量就不一样了（刚开始学习二分法的时候我经常纠结这个问题，和另外一个长度除2得到的是最中间的数吗的问题，我相信不止我一个人纠结过……但其实这是同一个问题，每次长度除2，如果长度为奇数，得到的中间的数字两边数字数量相同，如果长度为偶数就为上图中间的数字两边的相差为 1）

但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题，因为：

• 两边数量不一样是一定会出现的情况
• 但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
  • 只要中间数字大于目标数字，就排除右边的
  • 只要中间数字小于目标数字，就排除左边的

所以数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字

• 真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

3. 第一种写法（左闭右闭）

二分法最重要的两个点：

• while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
• 迭代过程中 middle 和 right 的关系，到底是 right = middle - 1 还是 right = middle

3.1 正向写法（正确演示）

第一种写法：每次查找的区间在[left, right]（左闭右闭区间），根据查找区间的定义（左闭右闭区间），就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]区间，所以有如下两点：

• 循环条件要使用while(left <= right)，因为当(left == right)这种情况发生的时候，得到的结果是有意义的
• if(nums[middle] > target) ， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left, middle - 1]

代码如下：

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{
    int left = 0;
    int right = size - 1;	// 定义了target在左闭右闭的区间内，[left, right]
    while (left <= right) {	//当left == right时，区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (nums[middle] > target) {
            right = middle - 1;	//target在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1;	//target在右区间，所以[middle + 1, right]
        } else {	//既不在左边，也不在右边，那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

下面图解算法的实现过程，建议将代码复制到一个文本编辑器中，边看代码边看图。或者我直接准备了图片，保存下来打开看就好了。

首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target 的值就是33

• 首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值
  • left = 0, right = size - 1
  • middle = (left + (right - left) / 2 )

• 比较 nums[middle] 的值和 target 的值大小关系

  • if (nums[middle] > target)，代表middle向右所有的数字大于target
  • if (nums[middle] < target)，代表middle向左所有的数字小于target
  • 既不大于也不小于就是找到了相等的值

• nums[middle] = 13 < target = 33，left = middle + 1

• 见下图：

• 循环条件为 while (left <= right)

• 此时，left = 6 <= right = 11，则继续进行循环

• 当前，middle = left + ((right - left) / 2)，计算出 middle 的值
  

• 计算出 middle 的值后，比较 nums[middle] 和 target 的值，发现：

  • nums[middle] = 33 == target = 33，找到目标

3.2 反向写法(错误演示)

对应第一种正向的写法，我们把循环条件修改看看会发生什么事

• 原查找区间 [left, right]
• 原循环条件是 while (left <= right)

修改后题目对应的条件：

• 查找区间不变，仍然是[left, right]
• 查找数字为27 (target = 27)
• 循环条件修改为while (left < right)

代码：

int search(int nums[], int size, int target) 
{
    int left = 0;
    int right = size - 1;	
    while (left < right) {	//left <= right 修改为 left < right,其他不变
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {	
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

代码图片，边看模拟过程边看代码哦！

好了，现在开始用图片模拟过程

• 初始化一个数组，计算 middle 的值

• 根据计算的 middle 值确定 nums[middle]

• 因为nums[middle] = 13 < target = 27，所以left = middle + 1

• 继续计算 middle 的值

• 因为 nums[middle] = 33 > target = 27，所以 right = middle - 1

• 接着计算 middle 的值

• 因为 nums[middle] = 22 < target = 27，此时 left = middle + 1，此时 left = right，而循环条件为while (left < right)，所以还未找到27 的情况下算法就跳出了循环，返回 -1

---

4. 第二种写法（左闭右开）

4.1 正向写法（正确演示）

第二种写法：每次查找的区间在 [left, right)，（左闭右开区间）， 根据区间的定义，条件控制应该如下：

• 循环条件使用while (left < right)
• if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

代码如下：

int search(int nums[], int size, int target)
{
	int left = 0;
	int right = size; //定义target在左闭右开的区间里，即[left, right)
	while (left < right) {	//因为left = right的时候，在[left, right)区间上无意义
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) {
			right = middle; //target 在左区间，在[left, middle)中 
		} else if (nums[middle] < target) {
			left = middle + 1;
		} else {
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片：保存下来边看代码边看图片演示过程

• 需要查找的值为3

第一步是初始化 left 和 right 的值，然后计算 middle 的值

• left = 0, right = size
• 循环条件while (left < right)

因为是左闭右开区间，所以数组定义如下：

• 计算 middle 的值，

• 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3
• 所以 right = middle

• 符合循环的条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 9 > target = 3
• 所以 right = middle

• 符合循环的条件，继续计算 middle 的值

• 比较 nums[middle] 和 target 的大小关系：因为nums[middle] = 0 < target = 3
• 所以 left = middle + 1

• 符合循环条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的关系：nums[middle] = 3 == target = 3
• 成功找到 target

4.2 反向写法（错误演示）

对应第二种正确的写法，照样把循环条件修改，看会发生什么事

正确的写法中条件为：

• 查找原区间 [left, right)
• 循环条件为 while (left < right)

修改后题目对应的条件：

• 查找区间不变，仍然是 [left, right)

• 循环条件修改为：while (left <= right)

• 查找的数字为26（数组中不存在这个数字！！！）

代码：

int search(int nums[], int size, int target)
{
	int left = 0;
	int right = size; 
	while (left <= right) {	//条件left < right 修改为 left <= right
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) {
			right = middle; 
		} else if (nums[middle] < target) {
			left = middle + 1;
		} else {
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片：（记得边看边保存图片代码边看图片演示哦！）

以下是演示全过程：

• 同样，开始初始化一个数组

• 先计算 middle 的值

• 判断 nums[middle] 和 target 的大小关系：nums[middle] = 22 < target = 26
• left = middle + 1 （其实这里nums[left] 已经等于27，26不可能找到，接下去就看算法是否能够知道数组中不存在26并且返回-1 了）

• 符合循环条件，计算 middle 的值

• 判断 nums[middle] 和 target 的大小关系：nums[middle] = 57 > target = 26
• right = middle

• 满足循环条件，接着计算 middle 的值

• 比较 nums[middle] 和 target 的大小关系：nums[middle] = 33 > target = 26
• right = middle

• 符合循环条件，继续计算 middle 的值

• 比较 nums[middle] 和 target 大小关系，因为 nums[middle] = 27 > target = 26，
• 所以 right = middle，自此，left 和 right 相遇，但是循环条件被我们修改成 while (left <= right) 会接着做循环

• 接下来就是死循环

• 因为 middle = left + ((right - left) / 2)，当 left = right 的时候，middle 的值不会继续改变

• middle 不继续改变，由于right = middle，right 也不会改变，所以三个数字自此开始不会继续改变

• 循环条件 while (left <= right) 却仍然满足，不会跳出循环

• 死循环……

5. 总结

二分法最重要的两个点，就是循环条件和后续的区间赋值问题

因为两者是相互联系，相互影响的，所以就需要两者统一，如果两者不统一，就会出现问题

所以循环条件和赋值问题必须统一，也就是循环不变量。

相关题目推荐：

• 35.搜索插入位置
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 69. x 的平方根
• 367.有效的完全平方数

本文相关信息:

• 算法学习自微信公众号:“代码随想录”
• 画图软件:Diagrams
• 代码生成图片软件:Carbon

❤️完结撒花❤️