前言

二分法，這一看似簡單卻又充滿哲理的算法，猶如一道精巧的數(shù)學之門，帶領(lǐng)我們在問題的迷霧中找到清晰的道路。它的名字雖簡單，卻深藏著智慧的光輝。在科學的浩瀚星空中，二分法如一顆璀璨的星辰，指引著我們?nèi)绾胃咝У貙ふ掖鸢?。本文將帶領(lǐng)大家走進二分法的世界，探討它的原理、應(yīng)用及其在各種問題中的深遠影響。

一. 原理講解

二分法，顧名思義，是將一個問題或區(qū)間不斷地分成兩個部分，逐步逼近目標答案。最常見的應(yīng)用是求解有序數(shù)列中的某個元素，或者求解某個函數(shù)的零點。
其基本思路如下：

• 初始化區(qū)間： 在一維空間中，選擇一個包含目標值的初始區(qū)間。
• 逐步縮小區(qū)間： 將區(qū)間分為兩半，判斷目標值是否在左半?yún)^(qū)間或右半?yún)^(qū)間中，根據(jù)判斷結(jié)果進一步縮小搜索區(qū)間。
• 終止條件： 直到找到目標值或區(qū)間縮小到足夠小為止。

這種“分而治之”的策略，極大地提高了搜索效率，尤其在處理大規(guī)模數(shù)據(jù)時，具有顯著的優(yōu)勢。

下面我們將結(jié)合具體題型進行二分法的使用與講解。

二. 二分查找

2.1 題目鏈接：https://leetcode.cn/problems/binary-search/description/

2.2 題目分析：

1. 題目中給出一個升序排列的數(shù)組，其中元素有正有負
2. 要求查找并返回數(shù)組內(nèi)與target相同的元素的下標
3. 如果不存在，則返回-1
4. nums內(nèi)的所有元素都不重復

2.3 思路講解

暴力解法：

此題較為簡單，查找目標值，直接遍歷即可，且數(shù)據(jù)量不大，應(yīng)該不會超時，不再給出示例代碼。

二分法：

1. 根據(jù)上文提到的原理可知，我們首先需要確定左右邊界，因此令left=0,right=nums.size()-1.
2. 由于該題數(shù)組為升序排列，二分之后具有二段性，即mid左側(cè)區(qū)間內(nèi)所有元素都小于mid，而mid右側(cè)區(qū)間內(nèi)所有元素都大于mid
3. 因此我們進行while循環(huán)，逐次二分判斷即可。如果循環(huán)期間內(nèi)未成功返回target的下標，說明不存在，反之，返回mid即可。

代碼實現(xiàn)：

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;//確定左右邊界//由于兩個指針相交時還未判斷是否等于target，因此需要取等號while(left<=right){int mid=(left+right)/2;if(nums[mid]>target){right=mid-1;}//更新右邊界else if(nums[mid]<target){left=mid+1;}//更新左區(qū)間else{return mid;}}return -1;}
};

三. 在排序數(shù)組中查找元素的第一個和最后一個位置

3.1 題目鏈接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

3.2 題目分析：

1. 題目給出按照升序排列的數(shù)組nums以及目標值target，要求返回target在數(shù)組內(nèi)的起始下標和結(jié)束下標。
2. 如果不存在，則返回{-1,-1}
3. 時間復雜度要求為logn。

3.3 思路講解：

問題：時間復雜度的要求和數(shù)組的二段性已經(jīng)很明顯的提示我們需要使用二分法，可是二分法我們只嘗試過查找單個target，面對一連串的target，我們又該如何處理呢？

雖然我們要查找的target是一串區(qū)間，但是數(shù)組仍滿足二段性，在target起始區(qū)間的左側(cè)，所有元素均小于target,而在target結(jié)束區(qū)間的右側(cè)，所有元素均大于target。

因此，我們使用兩次二分，分別查找該區(qū)間的左右邊界即可，具體步驟如下：

• 仍舊令left=0,right=nums.size()-1，確定左右區(qū)間進行二分查找

• 查找target的起始下標（左邊界)如圖：

• 

• 查找target的結(jié)束下標(右邊界）如圖：

• 

代碼實現(xiàn)：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0){return {-1,-1};}int left=0,right=nums.size()-1;int begin=0;//查找左邊界while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}//更新leftelse{right=mid;}//更新right}if(nums[left]!=target){return {-1,-1};}//若左邊界未查找成功，說明不存在target，直接返回begin=left;//查找成功，更新左邊界//查找右邊界right=nums.size()-1;//將right恢復為初始狀態(tài)while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]==target){left=mid;}//更新leftelse{right=mid-1;}//更新right}return {begin,right};}
};

四. x的平方根

4.1 題目鏈接：https://leetcode.cn/problems/sqrtx/description/

4.2 題目分析：

• 給出x，要求計算x的算術(shù)平方根
• 結(jié)果只保留整數(shù)部分，而非按照四舍五入規(guī)則
• x的范圍很大，使用int會存在越界情況
• x可能為0，此時應(yīng)特殊處理

4.3 思路講解：

我們可假設(shè)目標值為target，那么該題所有答案都在[0,n]的這個數(shù)組內(nèi)。

且[0,target]內(nèi)，所有元素的平方和均小于x,[target,x]內(nèi)，所有元素的平方和均大于x，即滿足二段性，因此可考慮使用二分法進行解決。
具體步驟如下：

1. 令left=1,right=x,確實左右區(qū)間進行遍歷
2. 進行取中點操作,mid=left+(right-left+1)/2,如果mid*mid>x，說明target在[left,mid]內(nèi)，right更新為mid-1.
3. 如果mid*mid<=x，說明target在[left,mid]內(nèi)，left更新為mid。
4. 進行循環(huán)遍歷，最終left即為所求。

4.4 代碼實現(xiàn)：

class Solution {
public:int mySqrt(int x) {int left=1,right=x;if(x==0){return 0;}while(left<right){long long mid=left+(right-left+1)/2;//防止越界if(mid*mid<=x){left=mid;}//更新leftelse{right=mid-1;}//更新right}return left;}
};

五. 山脈數(shù)組的峰頂索引

5.1 題目鏈接：https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

5.2 題目分析：

• 該數(shù)組呈山脈分布，設(shè)峰值元素為target，則[0,target]內(nèi)元素遞增,[target,n-1]內(nèi)元素遞減，要求返回峰值元素的下標
• 時間復雜度要求為logn

5.3 思路講解：

由上述分析不難發(fā)現(xiàn)可是用二分法。

1. 令left=1,right=nums.size()-2,作為左右邊界。
   注意：此處如此初始化是因為至少需要3個元素才能組成一個山峰，因此下標為0和下標為n-1的元素不可能為峰頂元素
2. 求取中點mid=left+(right-left+1)/2，并令nums[mid]與nums[mid-1]進行比較。

• 如果nums[mid]>=nums[mid-1]，說明mid處在上升區(qū)間內(nèi)，target一定位于[mid,right]內(nèi)，因此更新left為mid
• 如果nums[mid]<nums[mid-1]，說明mid處在下降區(qū)間內(nèi)，target一定位于[left,mid]內(nèi)，因此更新right為mid-1

3. while循環(huán)二分操作，最后left即為所求target

5.4 代碼實現(xiàn)：

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left=1,right=arr.size()-2;//峰頂元素即為最大值while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}//mid在上升區(qū)間內(nèi)else {right=mid-1;}}return left;}
};

六. 小結(jié)

6.1 局限性

盡管二分法在許多情況下都表現(xiàn)出極高的效率，但它也并非萬能。在應(yīng)用二分法時，要求數(shù)據(jù)必須是有序的，否則無法直接應(yīng)用。此外，二分法在處理某些特殊類型的問題時，可能需要額外的技巧或調(diào)整。例如，求解無序數(shù)據(jù)中的元素時，二分法并不能直接使用，需要先進行排序或采取其他的算法。

6.2 時間復雜度

二分法的時間復雜度為 O(log n)，這使得它在處理大規(guī)模數(shù)據(jù)時，具有非常高的效率。在最壞的情況下，每一步都將問題規(guī)模縮小一半，從而大大減少了運算的次數(shù)。與線性搜索相比，二分法能大幅度提高搜索效率，尤其是在數(shù)據(jù)量極大的情況下。

6.3 結(jié)語

二分法作為一種簡單而高效的算法，已經(jīng)成為計算機科學與數(shù)學中不可或缺的一部分。它不僅僅是一個算法工具，更是我們思考問題、解決問題的哲學。在這條“二分之間”的道路上，我們不僅找到了問題的解答，也探索到了求解問題的一種智慧。它教會我們，在復雜問題面前，不妨將問題拆解，逐步攻克，最終發(fā)現(xiàn)通往答案的光明之路。

本篇關(guān)于二分法的介紹就暫告一段落啦，希望能對大家的學習產(chǎn)生幫助，歡迎各位佬前來支持斧正！！！