《算法筆記》總結No.7——二分（多例題詳解版）

一.二分查找

????????目前有一個有序數列，舉個例子，假設是1~1000，讓我們去查找931這個數字，淺顯且暴力的做法就是直接從頭到尾遍歷一遍，直到找到931為止。當n非常大，比如達到100w時，這是一個非常大的量級，考慮到效率的優劣這是不能接收的。

? ? ? ? 二分查找是基于有序序列的一種查找算法，所謂的有序是序列嚴格遞增：每次根據當前查找區間的中位數來判斷是否與目標相同，如果不同就根據當前大小以上個區間的中點作為區間的某一端，繼續執行這個二分查找過程~

? ? ? ? 高效的點在于，二分的每一步都可以去除區間中一半的元素，其時間復雜度是O(logn)，學過數學的各位理科生都知道，對數的增加速度是非常慢的，甚至小于一次的冪函數，當N非常大的時候，越能體會到logN復雜度的含金量!

話不多說直接上代碼，依舊是博主自研的vector函數版：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void BinarySearch(vector<int> V,int x){int left=0;int right=V.size()-1;      //數組的末位 int i=(left+right)/2;     //初始中點 int flag=0;// flag為0意味著未查詢到 while(flag==0&&left<=right){cout<<"當前查詢的元素下標為："<<i<<endl;if(V[i]==x){cout<<i<<"位即為x的值~";flag=1;}else if(x>V[i])  //目標大于當前中點，中點的右一位+1作為新區間的左端點 {left=i+1;i=(left+right)/2;}else if(x<V[i])//目標小于當前中點，中點的左一位-1作為新區間的左端點{right=i-1;i=(left+right)/2;}					 }if(flag==0)cout<<"很遺憾，未找到~"<<endl;
} int main() {int n=0;vector<int> V;cout<<"請輸入數列規模："<<endl; cin>>n;for(int i=1;i<=n;i++) //讀入數據 {int temp=0;cin>>temp;V.push_back(temp); }sort(V.begin(),V.end());//排序一下，保證V本身有序！//其實這種題目直接就是有序~int x=0;cout<<"請輸入待查詢的值："<<endl;cin>>x;BinarySearch(V,x);return 0;
}

以書上的測試用例作為驗證組：

10

3 7 8 11 15 21 33 52 66 88?

11

首先給大家圖解畫一下過程，其實不難想象：

測試結果如下，沒什么bug：

????????tips：如果各位是考試或者寫什么數構的偽碼，其實用普通的數組就行，博主在實現的時候偏愛使用vector——這種隨時可以擴展的數組（向量）屬實給人極大的安全感，各位在閱讀的時候不要見怪~?

升級問題，假設序列中有多個相同的元素，請用二分法找到這個區間？（格式為左開右閉~）

其實和之前差不多，區別在于，我們要找到該元素第一次和最后一次出現的位置，因此之前的大小比較應該做出改善，如下：

找左端點時，還是用mid來與目標值對比，如果mid值大于等于目標值，則說明目標值第一次出現的位置有可能還要往左，因此還要往左查詢，因此要令right=mid（向左縮小范圍~）；如果mid比目標值小，則說明目標值第一次出現的位置還要再往右，應該令left=mid+1
找右端點時，如果mid>x，說明最后的目標數x在mid處或者mid的左側，因此應該在left~mid里面繼續找，即right=mid；如果mid小于等于x，說明最后一個x一定在mid的右側，因此令left=mid+1
其實兩者改變區間的方式一致，區別就在于改變的條件~

先是找左端點的函數：

int FindLeft(vector<int> V,int x){int left=0;int right=V.size()-1;      //數組的末位 int i=(left+right)/2;     //初始中點  while(left<right){//cout<<"當前查詢的元素下標為："<<i<<endl;if(V[i]>=x)   //如果當前值大于等于目標值，說明最小的有可能是mid或者mid的左邊{right=i;i=(left+right)/2;}else if(V[i]<x){left=i+1;//如果當前值小于目標值，說明最小的還要再往右i=(left+right)/2;	}}return left; 
}

然后是找右端點的函數：

int FindRight(vector<int> V,int x){int left=0;int right=V.size()-1;      //數組的末位 int i=(left+right)/2;     //初始中點 while(left<right){//cout<<"當前查詢的元素下標為："<<i<<endl;if(V[i]>x)   //如果當前值大于等于目標值，說明最大的有可能是mid或者mid的左邊{right=i;i=(left+right)/2;}else if(V[i]<=x){left=i+1;//如果當前值小于目標值，說明最大的可能還要再往右i=(left+right)/2;	}}return right; 
}

最后main函數調用：

int main() {int n=0;vector<int> V;cout<<"請輸入數列規模："<<endl; cin>>n;for(int i=1;i<=n;i++) //讀入數據 {int temp=0;cin>>temp;V.push_back(temp); }sort(V.begin(),V.end());//排序一下，保證V本身有序！//其實這種題目直接就是有序~int x=0;cout<<"請輸入待查詢的值："<<endl;cin>>x;cout<<x<<"的存在區間是："<<endl;cout<<"["<<FindLeft(V,x)<<","<<FindRight(V,x)<<")"<<endl;return 0;
}

兩組測試用例：

【1,2,2,2,3,3,3,3,3,4】——3
【0,0,0,1,2,2,2,2,3,3】——2

沒什么bug~

tips：其實寫成雙閉區間也可以，一個道理~修改一下if條件即可

一些注意事項：

在程序設計時，二分更多用的是非遞歸的設計方法
當上界超越int范圍的一半時，計算中點的left+right這一算式可能會導致溢出，這里修改的策略是mid=left+(right-left)/2
上面找左右端點的時候，需要將條件改為left<mid，不然會造成死循環

進一步思考上一步中尋找區間端點的過程：本質上，所有需要用到二分法的題目都是在解決：尋找有序序列中第一個滿足某條件元素的位置~?

????????如上，核心點就在于修改判斷的條件，這個條件，在序列中一定是從左到右先不滿足，然后滿足的過程~?

二.應用

1.方程根的近似值

先來看一個簡單的例子：求出根號n的近似值，也就是sqrt（n）。

與其用mid和sqrt（n）比，不如直接用mid平方和n比，再對mid開方，不難發現，這也是一個二分查找~

直接上代碼：

#include <iostream>
#include <cmath> 
using namespace std;void Calsqrt(int x)
{double n1=sqrt(x);cout<<x<<"的真實開根號值為:"<<n1<<endl;double left=trunc(n1),right=trunc(n1)+1;cout<<x<<"的取值范圍是:["<<left<<","<<right<<"]"<<endl;double i=0; while(right-left>0.0001)  //設置精度 {i=(left+right)/2;//初始中點 if((i*i)>x)  //目標大于待查找值，所以將上一個值作為右端點，查詢區間左移 right=i;	else //目標小于待查找值，所以將上一個值作為左端點，查詢區間右移left=i;}cout<<i<<endl;
}int main() {int n=0;cout<<"請輸入n的值:";cin>>n;Calsqrt(n);return 0;
}

注意點：

與真正的二分查找相比，本次的二分其實是針對一個連續的函數，因此所謂的left和right一定要為double型的，不然無效且死循環
同樣的道理，在改變區間時，直接用left或者right與mid相等就行——考過考研數學一的道友肯定知道，對于連續性的函數，端點處劃分到哪個區間都不影響！?

2.裝水問題

如上，其實還是一個同樣的問題，關鍵要找到一個切入點：隨著水高度h的增加，面積S是不斷增加的——這符合二分要求序列遞增的前提！

因此我們可以對h進行二分，并計算當前h下的面積與目標面積的差距，然后還是左右移動二分區間的套路，即可解決~

#include <iostream>
#include <cmath> 
using namespace std;#define Pi 3.14 void CalH(double R,double r)
{double sq1=R*R*Pi;//原始面積double sq2=sq1*r;//目標面積double answer=sq2/Pi;//設置一個中間值為目標h的平方倍 double i=0; //二分中點double left=0,right=R;// 二分區間 while(right-left>0.0001&&r<=1)  //設置精度 ,比例不能超過1 {i=(left+right)/2;//初始中點 if((i*i)>answer)  //目標大于待查找值，所以將上一個值作為右端點，查詢區間左移 right=i;	else //目標小于待查找值，所以將上一個值作為左端點，查詢區間右移left=i;}cout<<"目標h的值為："<<i<<endl;
}int main() {double R=0,r=0;cout<<"請輸入半徑的值:"<<endl;cin>>R;cout<<"請輸入比例的值:"<<endl;cin>>r;CalH(R,r);return 0;
}

這里我們選一個測試用例檢測一下：

沒什么問題~

3.木棒切割問題

還是老套路：找到遞增和目標值，兩個條件直接選用二分！

不難發現，當每一根木棒的長度越大時，分出來的個數肯定越小，因此應該用當前單體長度來進行二分，從小到大——當對應木棒的個數不符合題意中要求的個數時，則結束二分。

直接上代碼：

#include <iostream>
#include <vector>
#include <cmath> 
using namespace std;int Cut(vector<int>V,int k) //當前長度最多在數組中切多少~ 
{int count=0;for(int i=0;i<=V.size()-1;i++){int temp=0;temp=V[i]/k;count+=temp;	}	return count;
} void CalN(vector<int> V,int k)
{int min=V[0];for(int i=1;i<=V.size()-1;i++)if(V[i]<min)min=V[i];//找出最小值作為二分區間的右端點 int left=1,right=min;//最短也要長度為1，最長也超不過單體的最短~int i=0; //二分中點while(right-left>1)  //當差距是一位時，說明已經找到了，由于向下取整的原因會造成死循環，因此此時可以直接輸出中點的值 {i=(left+right)/2;//初始化中點if(Cut(V,i)>=k) //如果當前長度下的段數比目標的多，說明每一段的長度還可以再長,因此區間右移 	left=i;else          //如果當前的比目標的還少，應該縮短每一段的長度來增加個數，使得滿足要求~ right=i;		 	 }cout<<"最大長度為："<<i<<endl; }int main() {int num=0;vector<int> V;cout<<"請輸入木棒的個數:"<<endl;cin>>num;cout<<"請輸入每段木棒的長度:"<<endl;for(int i=1;i<=num;i++){int temp=0;cin>>temp;V.push_back(temp);}int K=0;cout<<"請輸要求長度相等的木棒個數:"<<endl;cin>>K;CalN(V,K); return 0;}

測試就用書上的測試兩次：

和手算的結果一致，沒什么問題：

三.快速冪

????????快速冪，顧名思義，一種快速計算冪函數的方法。博主的個人理解是，這玩意既像二分的思想，又像遞歸的思想，因此也可以稱之為二分冪~

現有數2的10000000次方，我們當然不能把2累乘10000000次——這是相當失敗的程序。其實中間有很多步驟可以省略：

當指數是偶數時，我們可以讓指數除以2，底數乘以底數；
當指數是奇數時，我們可以將指數變為偶數；

舉個例子，2的10次方，使用快速冪的思想，計算過程如下：

2的10次方，10是偶數，此時待算式為：4的5次
5為奇數，因此待算式為：4*4的4次
4為偶數，因此待算式為：4*16的2次
2為偶數，因此待算式為：4*16*256的一次
1為奇數，因此待算式為：4*16*256*256的0次，直接計算出來~

不難發現，上述過程只需要5步，而累乘需要10步，當指數變得非常大時，這一優勢會愈加明顯~

代碼如下：

1.非遞歸形態

#include<iostream>
using namespace std;
long long fpow(long long a,long long b){//a是底數，b是指數 long long ans=1;//初始化答案為1while(b){//當指數不為0時執行if(b%2==0){//指數為偶數時，指數除以2，底數乘以底數b/=2;a*=a; }else{//指數為奇數時，分離指數，ans乘以底數ans*=a; b--;}} return ans; 
}
int main(){long long n,m;cin>>n>>m;cout<<fpow(n,m)<<endl;
}

2.遞歸形態

#include<iostream>
using namespace std;
typedef long long LL;LL binaryPow(LL a,LL b)
{if(b==0) 	//遞歸邊界——即0次方 return 1;    if(b%2==1)   //奇偶各一次遞歸式 return a*binaryPow(a,b-1);else{LL mul =binaryPow(a,b/2);return mul*mul;}
}int main(){long long n,m;cin>>n>>m;cout<<binaryPow(n,m)<<endl;
}

tips：寫在最后

對于二分法的使用時機，主要要看兩個點：需要找到某個數值第一次或者最后一次出現的位置，且在尋找這個值的過程中，滿足該值單調遞增（遞減）
二分的循環條件，基本上都是right>left，或者作差大于某個值~
文中基本上全是博主根據偽碼自創的實現方式，博主酷愛使用vector，可能有些朋友看起來比較吃力；此外所有的mid都寫成了i，大家看的時候盡量理解~