做網(wǎng)站開發(fā)的有哪些公司好人工智能培訓課程
前言
二分法,這一看似簡單卻又充滿哲理的算法,猶如一道精巧的數(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 題目分析:
- 題目中給出一個升序排列的數(shù)組,其中元素有正有負
- 要求查找并返回數(shù)組內(nèi)與target相同的元素的下標
- 如果不存在,則返回-1
- nums內(nèi)的所有元素都不重復
2.3 思路講解
暴力解法:
此題較為簡單,查找目標值,直接遍歷即可,且數(shù)據(jù)量不大,應(yīng)該不會超時,不再給出示例代碼。
二分法:
- 根據(jù)上文提到的原理可知,我們首先需要確定左右邊界,因此令left=0,right=nums.size()-1.
- 由于該題數(shù)組為升序排列,二分之后具有二段性,即mid左側(cè)區(qū)間內(nèi)所有元素都小于mid,而mid右側(cè)區(qū)間內(nèi)所有元素都大于mid
- 因此我們進行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 題目分析:
- 題目給出按照升序排列的數(shù)組nums以及目標值target,要求返回target在數(shù)組內(nèi)的起始下標和結(jié)束下標。
- 如果不存在,則返回{-1,-1}
- 時間復雜度要求為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,即滿足二段性,因此可考慮使用二分法進行解決。
具體步驟如下:
- 令left=1,right=x,確實左右區(qū)間進行遍歷
- 進行取中點操作,mid=left+(right-left+1)/2,如果mid*mid>x,說明target在[left,mid]內(nèi),right更新為mid-1.
- 如果mid*mid<=x,說明target在[left,mid]內(nèi),left更新為mid。
- 進行循環(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)可是用二分法。
- 令left=1,right=nums.size()-2,作為左右邊界。
注意:此處如此初始化是因為至少需要3個元素才能組成一個山峰,因此下標為0和下標為n-1的元素不可能為峰頂元素- 求取中點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
- 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)生幫助,歡迎各位佬前來支持斧正!!!