前言
我身邊的人都認(rèn)為二分查找很簡(jiǎn)單，但事實(shí)真是如此嗎？不，并不簡(jiǎn)單。二分算法有著許多的邊界問題，當(dāng)你寫著代碼一不小心就會(huì)陷入死循環(huán)。本篇文章會(huì)深入細(xì)節(jié)詳細(xì)介紹整數(shù)二分算法以及使用二分算法步驟和力扣題目練習(xí)，并且還會(huì)給出二分查找算法模板，下面就然我們來看看吧。
一、二分查找算法介紹
1.二分算法的本質(zhì)
- 很多人認(rèn)為二分算法的本質(zhì)是單調(diào)性，其實(shí)并不是，二分和單調(diào)性的關(guān)系是：有單調(diào)性的題目一定可以二分，但是我可以二分的題目不一定非得有單調(diào)性，注意這句話非常重要，就是有單調(diào)性的話我可以二分，但是沒有單調(diào)性的話我也有可能可以二分。那么二分算法的本質(zhì)是什么呢？，二分算法的本質(zhì)其實(shí)是邊界。
單調(diào)性想必大家都不陌生，給出一段有序區(qū)間，找到它的中間值mid，如果中間值小于目標(biāo)值的話那么答案在右邊，如果中間值大于目標(biāo)值的話那么答案在左邊。
那么邊界又是個(gè)什么東西呢？我們給定一段區(qū)間，在這個(gè)區(qū)間上我們給定了一種性質(zhì)，使得在這個(gè)區(qū)間的右半邊是滿足這個(gè)性質(zhì)的，在這個(gè)區(qū)間的左半邊是不滿足這個(gè)性質(zhì)的。那么此時(shí)我們就可以使用二分，來找出滿足這個(gè)性質(zhì)和不滿足這個(gè)性質(zhì)的邊界點(diǎn)。
2.二分查找算法思想
算法思路：假設(shè)答案在閉區(qū)間[l, r]中， 每次將區(qū)間長(zhǎng)度縮小一半，當(dāng)l = r時(shí)，我們就找到了答案。
接著我們來看看二分算法的主要思想?，F(xiàn)在給我們一個(gè)區(qū)間，在這個(gè)區(qū)間上我們給定了一種性質(zhì)，使得在這個(gè)區(qū)間的右半邊是滿足這個(gè)性質(zhì)的，在這個(gè)區(qū)間的左半邊是不滿足這個(gè)性質(zhì)的。假設(shè)我們現(xiàn)在要找出左區(qū)間也就是紅色區(qū)間的邊界點(diǎn)，圖中用黃色點(diǎn)標(biāo)出了，我們應(yīng)該怎樣做呢？
首先我們先確定中間值mid，然后我們寫一個(gè)check函數(shù)，接著根據(jù)check函數(shù)更新答案所在區(qū)間。
此時(shí)mid是滿足紅色性質(zhì)的，所以mid落在紅色區(qū)間內(nèi)，所以mid是有可能為答案的，這里的答案指的是我們要而分出的邊界點(diǎn)也就是黃色點(diǎn)。所以此時(shí)答案所在區(qū)間就是[mid,R];那我們要更新答案區(qū)間，就要讓L=mid。
此時(shí)mid是不滿足紅色性質(zhì)的，所以mid沒有落在紅色區(qū)間內(nèi)，此時(shí)mid不可能為答案，所以此時(shí)答案所在區(qū)間就是[L,mid-1];那我們要更新答案區(qū)間，就要讓R=mid-1。
- 我們每一次更新區(qū)間都會(huì)使答案落在更新的區(qū)間內(nèi)，那么當(dāng)區(qū)間[ L , R ]只有一個(gè)數(shù)時(shí)，也就是L==R時(shí)，那么區(qū)間[ L , R ]中的那個(gè)數(shù)就是我們要找的答案。
二、二分查找算法模板?。。?/h2>
下面是二分查找算法的模板，這個(gè)模板幾乎可以勝任所有的二分題，建議背過。
版本1
當(dāng)我們將區(qū)間[l, r]劃分成[l, mid]和[mid + 1, r]時(shí)，其更新操作是 r = mid，計(jì)算mid時(shí)不需要加1。
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
版本2
當(dāng)我們將區(qū)間[l, r]劃分成[l, mid - 1]和[mid, r]時(shí)，其更新操作是l = mid;，此時(shí)為了防止死循環(huán)，計(jì)算mid時(shí)需要加1。
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid =(l + r + 1)/2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
二分模板一共有兩個(gè)，分別適用于不同情況。但其本質(zhì)的區(qū)別就是mid = ( l + r ) / 2時(shí)需不要加上1。注意：當(dāng)更新操作為其更新操作是 r = mid，計(jì)算mid時(shí)不需要加1。其更新操作是l = mid;，此時(shí)為了防止死循環(huán)，計(jì)算mid時(shí)需要加1。
加上1的目的是為了防止死循環(huán)，這個(gè)我們會(huì)在后面的題目解釋。
那么這個(gè)兩個(gè)模板要怎么使用呢？ 我們來做幾道題目，從這幾道題目中我來給你們解釋。
三、力扣題目練習(xí)
704. 二分查找
–>題目鏈接
這道題目的前提是數(shù)組為有序數(shù)組，同時(shí)題目還強(qiáng)調(diào)數(shù)組中無重復(fù)元素，因?yàn)橐坏┯兄貜?fù)元素，使用二分查找法返回的元素下標(biāo)可能不是唯一的，這些都是使用二分法的前提條件，當(dāng)大家看到題目描述滿足如上條件的時(shí)候,就要考慮是不是可以用二分法了。
這里我們看了題目，發(fā)現(xiàn)可以使用二分法。那么我們就用剛剛的模板來看看吧，那要怎么用呢？
- 首先我們先確定中間值mid
- 然后我們寫一個(gè)check函數(shù)
- 接著根據(jù)check函數(shù)更新答案所在區(qū)間。
- 根據(jù)更新操作判斷需不需要加上1
首先我們先確定中間值mid,現(xiàn)在有一區(qū)間[-1，12]，我們定義左端點(diǎn)和右端點(diǎn)，接著我們計(jì)算出mid的值為（0+5）/2=2;
接著我們寫一個(gè)check函數(shù),可以看到target為9，那么此時(shí)區(qū)間是不是滿足一個(gè)性質(zhì)，這個(gè)性質(zhì)把區(qū)間分為兩部分，藍(lán)色部分的值小于9，綠色區(qū)間的值大于等于9。 此時(shí)我們這個(gè)check函數(shù)可以定義為if(mid的值>=9)，就是判斷mid是不是滿足大于等于9這個(gè)性質(zhì)。
如果mid滿足這個(gè)特性就說明它落在綠色區(qū)域，此時(shí)我們就要更新答案所在區(qū)間，此時(shí)答案在[L，mid]中，我們的更新操作為R=mid;由于更新操作是R=mid,所以這里的mid = ( l + r ) / 2時(shí)不需要加上1!!!,我們自然而然使用第一個(gè)模板。
但此時(shí)mid的下標(biāo)為2所對(duì)應(yīng)的值時(shí)3，它是不滿足>=9這個(gè)性質(zhì)的，所以mid此時(shí)落在藍(lán)色區(qū)域,此時(shí)我們就要更新答案所在區(qū)間，此時(shí)答案在[mid，R]中，我們的更新操作為L=mid+1;
然后我們不斷縮小答案所在范圍，直到這個(gè)區(qū)間只有一個(gè)數(shù)時(shí)也就是L==R,那此時(shí)區(qū)間內(nèi)唯一的那個(gè)數(shù)就是我們要找的答案，也就是這個(gè)性質(zhì)的邊界點(diǎn)。
看看代碼實(shí)現(xiàn)
int l=0,r=nums.size()-1;
while(l < r)
{
int mid = (l + r) /2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
但是當(dāng)我們提交答案后，發(fā)現(xiàn)這個(gè)測(cè)試樣例出錯(cuò)了。
-
target為2，但是這個(gè)區(qū)間內(nèi)并沒有2，那我們此時(shí)二分查找出來的邊界點(diǎn)是什么呢？
-
我們?cè)倩氐絼倓偟臉永覀冎蓝植檎业谋举|(zhì)是處理邊界問題，我們給這段區(qū)間一個(gè)性質(zhì)，那么這個(gè)性質(zhì)是一定有邊界的，所以二分是一定有解的。這里我們找到的性質(zhì)是target右邊是大于等于9的，target左邊是小于9的,這個(gè)性質(zhì)把區(qū)間分為了兩部分，綠色部分是滿足這個(gè)性質(zhì)的，藍(lán)色部分是不滿足這個(gè)性質(zhì)的。那么我們這里的二分查找出來的這個(gè)值就是這個(gè)性質(zhì)的邊界點(diǎn)。
-
現(xiàn)在我們回到剛剛報(bào)錯(cuò)的測(cè)試樣例，那如果這個(gè)區(qū)間里沒有這個(gè)target呢？我們二分查找出來的這個(gè)值就是這個(gè)性質(zhì)的邊界點(diǎn)，此時(shí)我們的的性質(zhì)是target右邊是大于等于2的，target左邊小于2的，也就是說我們會(huì)找到這個(gè)區(qū)間里從左往右第一個(gè)大于等于2的點(diǎn)。 這句話很重要，請(qǐng)重復(fù)理解。因此我們找到的值為3，它的下標(biāo)為2，與預(yù)期結(jié)果-1不符，所以錯(cuò)誤。
-
對(duì)此我們可以加一個(gè)判斷條件，如果我們二分出來的值不等于target的話就return-1；
完整代碼
int l=0,r=nums.size()-1;
while(l < r)
{
int mid = (l + r) /2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[l] != target) return -1;
return l;
35.搜索插入位置
–題目鏈接
這道題目的前提是數(shù)組為有序數(shù)組，同時(shí)題目還強(qiáng)調(diào)數(shù)組中無重復(fù)元素，因?yàn)橐坏┯兄貜?fù)元素，使用二分查找法返回的元素下標(biāo)可能不是唯一的，這些都是使用二分法的前提條件，當(dāng)大家看到題目描述滿足如上條件的時(shí)候,就要考慮是不是可以用二分法了。 這里我們?cè)俅翁崞疬@句話，什么時(shí)候考慮使用二分。
- 可以看到這一題和上一題基本一致，唯一的區(qū)別就是這題如果我們的target不在這個(gè)區(qū)間內(nèi)，我們就需要返回它將會(huì)被按順序插入的位置的下標(biāo)。
- 仔細(xì)想想，二分查找是一定有解的，這個(gè)解就是區(qū)間內(nèi)性質(zhì)的邊界點(diǎn)。
- 那么如果這個(gè)區(qū)間內(nèi)沒有這個(gè)target這個(gè)值，我們是不是二分出來的是這個(gè)區(qū)間里從左往右第一個(gè)大于等于target的點(diǎn)呢，這不正好就是我們要插入的位置嗎。
解題過程
- 首先我們先確定中間值mid
- 然后我們寫一個(gè)check函數(shù)
- 接著根據(jù)check函數(shù)更新答案所在區(qū)間。
- 根據(jù)更新操作判斷需不需要加上1
看看代碼
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
return l;
但是當(dāng)我們提交后，沒錯(cuò)，又有錯(cuò)誤??！
- 此時(shí)target值為7，區(qū)間內(nèi)沒有7這個(gè)值，那我們二分到的應(yīng)該是大于等于7的第一個(gè)位置，但此時(shí)我們發(fā)現(xiàn)區(qū)間內(nèi)最大的數(shù)為6，6是這個(gè)區(qū)間的最后一個(gè)位置，也就是說我們的L和R不能再往后更新了，此時(shí)L和R落在6的這個(gè)位置，循環(huán)結(jié)束，我們返回的是6的下標(biāo)也就是3，但我們的7應(yīng)該插入到6的后一個(gè)位置，也就是下標(biāo)為4的位置。
- 解決方法，我們做一個(gè)特殊判斷，如果target的值大于區(qū)間最后一個(gè)元素的值那我們直接返回?cái)?shù)組最后一個(gè)元素的下標(biāo)加1；
完整代碼
int l=0,r=nums.size()-1;
if(nums[r]<target)
return r+1;
while(l<r)
{
int mid=l+r>>1;
if(nums[mid]>=target) r=mid;//此時(shí)更新方式是r=mid,所以求mid不需要加上1
else l=mid+1;
}
return l;
34.在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
題目鏈接
這道題目是什么意思呢？假設(shè)我們有一組數(shù)據(jù)，[5，7，7，8，8，10],此時(shí)target=8,那我們就返回?cái)?shù)據(jù)中8的開始下標(biāo)和結(jié)束下標(biāo)。若數(shù)據(jù)內(nèi)不存在target則返回[-1，-1]。
老規(guī)矩，看做題步驟。
解題過程
- 首先我們先確定中間值mid
- 然后我們寫一個(gè)check函數(shù)
- 接著根據(jù)check函數(shù)更新答案所在區(qū)間。
-
根據(jù)更新操作判斷需不需要加上1
由于我們要尋找開始下標(biāo)和結(jié)束下標(biāo)兩個(gè)位置，所以我們肯定需要倆個(gè)二分算法，一個(gè)尋找開始下標(biāo)，一個(gè)尋找結(jié)束下標(biāo)，這里我們分開來分析。
首先是尋找開始下標(biāo)，就拿上面圖片的樣例來分析，此時(shí)這個(gè)區(qū)間是不是被一個(gè)性質(zhì)分成了兩部分，這個(gè)性質(zhì)是什么呢，可以看到開始下標(biāo)左邊的數(shù)都是小于8的，開始下標(biāo)右邊的數(shù)都是大于等于8的，這個(gè)性質(zhì)把區(qū)間分為了兩個(gè)部分，我們用二分就可以找出這個(gè)性質(zhì)的邊界點(diǎn)，也就是這里的開始下標(biāo)的位置。
那么具體代碼是什么呢？
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
接著是尋找結(jié)束下標(biāo)，此時(shí)這個(gè)區(qū)間是不是被一個(gè)性質(zhì)分成了兩部分，這個(gè)性質(zhì)是什么呢，可以看到結(jié)束下標(biāo)左邊的數(shù)都是大于等于8的，結(jié)束下標(biāo)右邊的數(shù)都是大于8的，這個(gè)性質(zhì)把區(qū)間分為了兩個(gè)部分，我們用二分就可以找出這個(gè)性質(zhì)的邊界點(diǎn)，也就是這里的結(jié)束下標(biāo)的位置。
下面是具體代碼
可以看到更新方式為L(zhǎng)=mid;所以這里的mid = ( l + r ) / 2時(shí)需要加上1，這里我們就使用了第二個(gè)模板。
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
下面是完整代碼
vector<int> res;
//如果我們的數(shù)據(jù)為空，直接返回[-1,-1]
if(nums.size()==0)
{
res.push_back(-1);
res.push_back(-1);
return res;
}
//二分開始下標(biāo)
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
//當(dāng)target值不存在時(shí)，return[-1,-1]
if(nums[l]!=target)
{
res.push_back(-1);
res.push_back(-1);
return res;
}
res.push_back(l);
//二分結(jié)束下標(biāo)
l=0,r=nums.size()-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
res.push_back(l);
return res;
為什么要加上1
好了，三道題目做完了，不知道你還記得那兩個(gè)模板嗎，一個(gè)模板在求mid是需要加上一，一個(gè)不需要。但是你知道為什么嗎?其實(shí)在前面我已經(jīng)提到過了，是為了防止死循環(huán)所以我們加上了一個(gè)1，下面我們來分析下;
- 我們知道當(dāng)更新方式為L(zhǎng)=mid時(shí)，這里的mid = ( l + r ) / 2時(shí)需要加上1。
- 如果此時(shí)L=R-1,那么mid算出來的結(jié)果應(yīng)該為L(zhǎng);這里我們可以帶入數(shù)據(jù)去計(jì)算，當(dāng)L=3,R=4,此時(shí)mid=(3+4)/2等于3，然后我們更新答案區(qū)間，L=mid,我們就又把3賦值給了L,此時(shí)就陷入了死循環(huán)。
- 所以我們需要在這里加上1，此時(shí)mid的值就為（3+4+1）/2等于4,然后我們更新答案區(qū)間，L=mid,此時(shí)就把4賦值給了L,這時(shí)候L==R,循環(huán)就終止了，我們就找到了邊界點(diǎn)。
四.浮點(diǎn)數(shù)二分算法模板
以上我們介紹的都是整數(shù)二分算法，整數(shù)二分算法需要考慮許多邊界問題，因此細(xì)節(jié)比較多，但浮點(diǎn)數(shù)二分簡(jiǎn)單多了。這里我們就去介紹了，同樣的我會(huì)給出浮點(diǎn)數(shù)二分算法的模板。
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取決于題目對(duì)精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
這里有兩道題目，大家可以自己去嘗試做一做。
69.x 的平方根
367.有效的完全平方數(shù)
記住我們的做題步驟，然后套用上面的模板。
解題過程
- 首先我們先確定中間值mid
- 然后我們寫一個(gè)check函數(shù)
- 接著根據(jù)check函數(shù)更新答案所在區(qū)間。
- 根據(jù)更新操作判斷需不需要加上1
總結(jié)
- 本篇文章介紹了整數(shù)二分算法，二分算法的本質(zhì)不是單調(diào)性，二分和單調(diào)性的關(guān)系是：有單調(diào)性的題目一定可以二分，但是我可以二分的題目不一定非得有單調(diào)性，二分算法的本質(zhì)是處理邊界。
- 算法思路：假設(shè)答案在閉區(qū)間[l, r]中， 每次將區(qū)間長(zhǎng)度縮小一半，當(dāng)l = r時(shí)，我們就找到了答案。
- 然后我們給出了整數(shù)二分算法的模板和浮點(diǎn)數(shù)二分算法的模板，整數(shù)二分的模板是由兩個(gè)的，其本質(zhì)的區(qū)別就是mid = ( l + r ) / 2時(shí)需不要加上1，這個(gè)模板幾乎可以用來解決所有的二分題，建議背過。
- 接著我們做了幾道力扣題，還記得我們的做題步驟嗎。
- 首先我們先確定中間值mid
- 然后我們寫一個(gè)check函數(shù)
- 接著根據(jù)check函數(shù)更新答案所在區(qū)間。
- 根據(jù)更新操作判斷需不需要加上1
然后我們分析了整數(shù)模板為什么需要加上1，其原因是為了防止死循環(huán)。文章來源：http://www.zghlxwxcb.cn/news/detail-409674.html
好了，這篇文章就分享到這，如果對(duì)你有幫助的話，請(qǐng)點(diǎn)贊關(guān)注，支持一下吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-409674.html
到了這里，關(guān)于二分查找算法 | 你真的搞懂二分了嗎?的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
