首先，什么是二分法：

? ? ? ? 最簡(jiǎn)單的例子就是類似于二分查找的用法來(lái)實(shí)現(xiàn)快速查找有序區(qū)間內(nèi)的給定的目標(biāo)值是否存在，當(dāng)然，這也可以應(yīng)用在別的問(wèn)題中，二分查找是一個(gè)時(shí)間效率極高的算法，尤其是面對(duì)大量的數(shù)據(jù)時(shí)，其查找效率是極高，時(shí)間復(fù)雜度是log(n)。如果問(wèn)題是單調(diào)的，且求解精確解的難度很高，可以考慮用二分法。
主要思想就是不斷的對(duì)半折疊，每次查找都能除去一半的數(shù)據(jù)量，直到最后將所有不符合條件的結(jié)果都去除，只剩下一個(gè)符合條件的結(jié)果。

二分法看似簡(jiǎn)單，實(shí)則在細(xì)節(jié)上非常容易出錯(cuò)，要注意終止邊界，左右區(qū)間開閉情況，避免漏掉答案和陷入死循環(huán)，在了解了最簡(jiǎn)單的基本原理之后，我們來(lái)由簡(jiǎn)入繁地以題目來(lái)入手理解這個(gè)算法，

1.關(guān)鍵的mid的處理

在整個(gè)二分法中，對(duì)于mid的處理至關(guān)重要，如果取值不當(dāng)，while很容易會(huì)死循環(huán)，我們來(lái)分三點(diǎn)討論這個(gè)問(wèn)題：

1.1left=mid+1能否寫成left=mid？

? ? ?在實(shí)數(shù)二分中，確實(shí)是left=mid，right=mid，但是在整數(shù)二分中存在取整問(wèn)題，如果取left=mid，會(huì)造成原來(lái)的left和right值不改變，所以while循環(huán)會(huì)一直進(jìn)行下去造成死循環(huán)，取left=mid+1則不會(huì)。

1.2 不同問(wèn)題下的mid取值問(wèn)題

? ? 我們要根據(jù)不同的問(wèn)題來(lái)識(shí)別到底需要左中位數(shù)還是右中位數(shù)，即對(duì)于mid的取值，我們可以向上取整同樣的也可以向下取整，要看具體問(wèn)題的邏輯，我們一般的都使用左中位數(shù)，即靠近left的那個(gè)數(shù)；

1.3謹(jǐn)慎使用（left+right）/2

我們都知道，除法的取整會(huì)導(dǎo)致在正負(fù)區(qū)間左右的中位數(shù)計(jì)算不一致，雖然一般的情況下，left和right都是正數(shù)，在實(shí)際計(jì)算中，我們可以用mid=left+（right-left）/2或者是mid=（left+right）>>1來(lái)替換即可，綜合來(lái)看，還是（left+right）>>1更優(yōu)。

下面我們還是來(lái)通過(guò)例題理解這些知識(shí)：

例題一

經(jīng)典的最大值最小化模型

?

?首先，我們?cè)鯓影讯址☉?yīng)用到這個(gè)題的求解中，我們知道這個(gè)題其實(shí)就是想讓我們?cè)趧澐值臄?shù)組中求出無(wú)論怎樣劃分，其每個(gè)分子數(shù)組產(chǎn)生的和都有一個(gè)確定的最小值，而這個(gè)最小值一定介于原數(shù)組中的最大的一個(gè)元素（最小劃分為一個(gè)數(shù)組）和原數(shù)組的所有數(shù)組元素的和（最大的一個(gè)分組）之間，我們可以在這兩個(gè)邊界之間枚舉我們的最大值，采用二分法來(lái)尋找最小的那一個(gè)數(shù)。

我們?cè)诖a中來(lái)解釋細(xì)節(jié)問(wèn)題

#include <cstdio>
#include <algorithm>
int n, m;
int l, r, mid, ans;
int a[100010];
//二分答案，枚舉出一個(gè)最大值，根據(jù)分組情況調(diào)整最大值，求出最優(yōu)最大值。
/*
 * check 函數(shù)
 * 作用:
 *		根據(jù)枚舉出的最大值，來(lái)分組，根據(jù)分出的組數(shù)來(lái)調(diào)整最大值
 * 變量:
 *		x : 枚舉出的最大值
 *		sum : 分組時(shí)每組的和
 *		count : 分出的組數(shù)
 */
bool check(int x)
{
    int sum=0, count=0;//t2: 組數(shù) t1: 每組的和
    for(int i=0; i<n; i++){
        if(sum+a[i]<=x)sum+=a[i]; //如果還是小于mid，就繼續(xù)加上去
        else //objective 1如果當(dāng)前sum已經(jīng)達(dá)到當(dāng)前最大值應(yīng)該怎么處理？
        {
		  sum=a[i]; //設(shè)置sum為當(dāng)前數(shù)字,相當(dāng)于換入下一組
		  count++;
        }
    }
   if(count>=m)return true;//objective 2 
   return false;
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
                r += a[i];
		l = std::max(l, a[i]);
	}
    while( l<=r ){
        mid=(l+r)/2;
        if( check(mid) )l=mid+1;//如果最后的count是大于m的話，說(shuō)明mid太小了，需要l往右移
        else {//否則就是mid太大了
			r=mid-1;
		}
    }
    printf("%d",l);
    return 0;
}

重點(diǎn)其實(shí)就在于思路上如何將其與二分法結(jié)合在一起考慮問(wèn)題。

例二

差分?jǐn)?shù)組+二分

?

?我們的注釋在題解中見

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
/*
 * line : 原數(shù)列
 * l, r, d, : 題目要求的 對(duì)于每個(gè)區(qū)間的左端點(diǎn) 右端點(diǎn) 值
 * change : 差分?jǐn)?shù)組
 * 題解：對(duì)采用的訂單數(shù)進(jìn)行二分，每次用差分?jǐn)?shù)組優(yōu)化處理當(dāng)天需要的教室數(shù)并與當(dāng)天可對(duì)外借出的教室數(shù)比較檢驗(yàn)。-Megumin
 */

int line[1000010], l[1000010], r[1000010], d[1000010], change[1000010];
int n, m;

int check(int x)
{
	memset(change, 0, sizeof(change));

	for (int i = 1; i <= x; i++)
	{
		change[l[i]] += d[i];
		change[r[i] + 1] -= d[i];
		//obj 1用差分?jǐn)?shù)組對(duì)前x個(gè)操作進(jìn)行處理 
	}

	//for (int i = 1; i <= n; i++)
	//	change[i] += (line[i] - line[i - 1]);
	//obj 2抹平差分?jǐn)?shù)組 ,此處不需要抹平差分?jǐn)?shù)組，我們只需要默認(rèn)為line數(shù)組全體為零，在將其和我們的change數(shù)組結(jié)合求出實(shí)際上需要的教室數(shù)量，再和原來(lái)的進(jìn)行對(duì)比看看是否不夠來(lái)判斷非法
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		sum += change[i];
		if (sum>line[i])return false;
		//printf("%d ", sum);
	}
	//obj 3什么情況下是發(fā)生了問(wèn)題？ 

	return true;
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &line[i]);

	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &d[i], &l[i], &r[i]);

	if (check(m))//obj 4什么情況是全都可以成立 
	{
		printf("0");
		return 0;
	}



	int left = 1, right = m, mid;
	while (left < right)
	{
		mid = (left + right) >> 1;
		if (check(mid))//obj 5	
		{
			left = mid+1;
		}
		else
		{
			right = mid;
		}
	}
	printf("-1\n");
	printf("%d", left);

	return 0;
}

當(dāng)然，二分法是一個(gè)沒有上限的算法，要是展開講的話肯定是講不完的，但是二分法的上限是如何將題目轉(zhuǎn)化為二分法進(jìn)行求解，又將誰(shuí)二分，上下限如何確定等問(wèn)題，只需要注意細(xì)節(jié)，剩下的就要靠日積月累來(lái)積累做題思維了。

例三 最小值最大問(wèn)題

跳石子

?

? ? ? ?我們的重點(diǎn)是在于怎么把這道題和二分法相結(jié)合起來(lái)，我們發(fā)現(xiàn)我們的取值范圍在1~l（也就是1~終點(diǎn)）處，我們可以通過(guò)二分這段距離，每得到一個(gè)中間值，判斷這個(gè)中間值所代表的的最短跳躍距離是不是合法，如果合法，那么我們的最短跳躍距離還在右邊，于是我們把left值改為mid+1，同理，如果我們的mid值不滿足，那么我們的最大值的產(chǎn)生一定在左邊的區(qū)間內(nèi)，于是將right置為mid-1；

? ? ?接著我們來(lái)思考這個(gè)判斷過(guò)程，我們知道只能移走m塊石頭，而且我們每移走一塊石頭，我們的原相鄰的兩塊石頭就會(huì)變化，這樣，我們可以采用類似雙指針的做法來(lái)判斷，具體的看代碼理解：

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
int a[maxn];
int l, n, m;
inline bool check(int x)
{
	int num = 0;
	int i = 0, j = 0;
	while (i <=n)
	{
		i++;
		if (a[i] - a[j] < x)//移走當(dāng)前石頭的同時(shí)，j將會(huì)與第i+1個(gè)元素相鄰所以下一次相比還是j
			num++;
		else
		{
			j = i;//接著找下一個(gè)
		}
		if (num > m)
			return false;
	}
	
	return true;
}
int main()
{
	scanf("%d%d%d", &l, &n, &m);
	for (int i = 1; i <=n; i++)
	{
		scanf("%d", &a[i]);
	}
	a[n + 1] = l;
	int left = 1, right = l;
	while (left <= right)
	{
		int mid = (left + right) >> 1;
		if (check(mid))
		{
			
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	printf("%d\n", left-1);
	return 0;
}

? ? ? ?我們總結(jié)二分法在解決實(shí)際問(wèn)題的應(yīng)用時(shí)，本質(zhì)上我們的二分法是在確定的區(qū)間內(nèi)枚舉所有可能的答案，我們尋找的最大最小值，往往就在我們二分判斷的結(jié)束階段產(chǎn)生。

金句省身

? ? ? ? 當(dāng)你被黑暗敲打的時(shí)候，恰好證明你就是光明本身，每一個(gè)優(yōu)秀的人，都會(huì)有一段沉默的時(shí)光，天賦決定下限，努力決定上限，生活給你壓力，你就還它奇跡。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? -----致不甘平凡的我們

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-740048.html

到了這里，關(guān)于二分法的原理及其應(yīng)用舉例的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！