前言

我在算法題目的海洋中暢游已久，也曾在算法競賽中榮獲佳績。然而，我發(fā)現(xiàn)自己對于算法的學(xué)習(xí)，還缺乏一個(gè)系統(tǒng)性的總結(jié)和歸類。盡管我已經(jīng)涉獵過不少算法類型，但心中仍舊覺得有所欠缺，未能形成完整的算法體系。

因此，我決定踏上這次算法之旅，對常見的算法進(jìn)行一次全面的梳理與歸類。我希望通過這個(gè)過程，能夠更深入地理解每個(gè)經(jīng)典算法類型的核心知識(shí)，加強(qiáng)我的算法能力，并完善自己的算法體系。

同時(shí)，我也希望能夠?qū)⑦@次學(xué)習(xí)的成果與你分享，希望對你也有所幫助。讓我們一同在算法的世界里探索、成長，共同迎接未來的挑戰(zhàn)吧！

1.經(jīng)典的不能在經(jīng)典的二分查找（難度?）

Leetcode鏈接：704. 二分查找

1.1題目描述：

? ? ?這是一道非常典型的二分查找算法題目,可以說所有要學(xué)習(xí)二分查找算法的人都必須掌握這道題。題目要求很簡單,就是在一個(gè)有序數(shù)組中查找目標(biāo)值target。這道題是二分查找算法的入門題和模版題,沒有掌握這道題就無法開始學(xué)習(xí)更復(fù)雜的二分查找算法題目。所以這道題對于二分查找算法的理解和掌握非常關(guān)鍵和必要。

1.2代碼：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;int mid;while(left <= right){mid = (left + right)/2;if(nums[mid]>target){right = mid - 1;}else if(nums[mid]<target){left = mid + 1;}else{return mid;}}return -1;}
};

通過這道二分查找的典型題,我對二分查找算法的理解更進(jìn)一步:

我對二分查找的區(qū)間劃分有了更深的理解:

• 當(dāng)mid位置的值小于target時(shí),證明左區(qū)間[left, mid-1]都不可能存在target,所以左區(qū)間變?yōu)閇mid+1, right]。
• 當(dāng)mid位置的值大于target時(shí),證明右區(qū)間[mid+1, right]都不可能存在target,所以右區(qū)間變?yōu)閇left, mid-1]。
• 當(dāng)mid位置的值等于target時(shí),就找到了目標(biāo)值。

我理解到二分查找的本質(zhì)就是通過比較中間mid值與target的值,可以排除一半的搜索區(qū)間,使搜索范圍越來越小,直到找到target。

通過這道題我對二分查找算法模板有了更加熟練的掌握,可以應(yīng)用到其他二分查找題目中去。

2.在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（難度??）

Leetcode鏈接：34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

2.1題目描述：

2.2代碼：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, begin = -1, end = -1, mid;//找到區(qū)間左邊界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{begin = mid;right--;//right區(qū)間左移，使得mid左移，直到到達(dá)左區(qū)間邊界，此時(shí)right正好和left重合}}left = 0, right = nums.size() - 1;//找到區(qū)間有邊界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{end = mid;left++;//left區(qū)間右移，使得mid右移，直到到達(dá)又區(qū)間邊界，此時(shí)left正好和right重合}}return {begin,end};}
};

這道題的大思路和上面的題并沒有太大區(qū)別，只是為了找到左右區(qū)間，需要兩次二分查找

具體來說,在求左右區(qū)間邊界時(shí),處理mid==target的情況需要進(jìn)行特別考慮:

• 求左區(qū)間邊界時(shí),需要在記錄begin索引后,繼續(xù)將right索引左移,使得mid向左逼近,直到不等于target時(shí)才能鎖定左區(qū)間邊界。
• 求右區(qū)間邊界時(shí),需要在記錄end索引后,繼續(xù)將left索引右移,使得mid向右逼近,直到不等于target時(shí)才能鎖定右區(qū)間邊界。

這種細(xì)微的邏輯調(diào)整體現(xiàn)了二分查找的靈活性,在保持模板框架不變的情況下,通過簡單邏輯修改就可應(yīng)對新的問題。

3.?有效的完全平方數(shù)（難度?）

Leetcode鏈接：367. 有效的完全平方數(shù)

3.1題目描述：

撇開具體問題不討論，假設(shè)需要找到完全平方數(shù)，你可能會(huì)采用這樣的方法：將原數(shù)進(jìn)行二分，然后將得到的中間值平方，觀察是否等于目標(biāo)值。如果相等，那么找到了完全平方數(shù)；如果不等，就可以根據(jù)大小關(guān)系縮小搜索范圍，繼續(xù)二分。為什么選擇這種方式呢？因?yàn)檫@種方法的效率相對較高。既然如此，我們?yōu)楹尾豢紤]運(yùn)用二分法來解決這類問題呢？

3.2代碼：

class Solution {
public:bool isPerfectSquare(int num) {long long left = 0, right = num, mid = 0;long long s;while(left<=right){mid = (left + right)/2;s = mid * mid;if(s>num){right=mid-1;}else if(s<num){left=mid+1;}else{return true;}}return false;}
};

在這個(gè)解決方案中，我們并沒有深入探討具體的代碼細(xì)節(jié)，只是簡單地將二分算法應(yīng)用于這個(gè)場景。然而，通過這個(gè)簡單的經(jīng)驗(yàn)，我們可以得出一個(gè)更加廣泛的啟示：如果今后遇到類似的問題，我們可以考慮運(yùn)用二分法。

4.尋找峰值（難度??）

二分熟練度up up up~

Leetcode鏈接：162. 尋找峰值

4.1題目描述：

在面對這個(gè)問題時(shí)，我們甚至沒有提供目標(biāo)值（target），而且輸入序列并不保證是有序的。這是否意味著我們可以應(yīng)用二分查找算法呢？
讓我們嘗試通過代碼來展示這一思路，看看是否能夠在這樣的條件下成功運(yùn)用二分查找的思想解決問題。

4.2代碼：

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1, mid = 0;while(left<right){mid = (left + right)/2;if(nums[mid]>nums[mid + 1]){right = mid;}else{left = mid + 1;}}return right;}
};

初看之下，面對問題好像難以著手，但讓我們仔細(xì)分析一下，看看能否找到解決方案。

題目要求在數(shù)組中找到任意一個(gè)峰值，那么我們可以考慮將數(shù)組分為兩個(gè)區(qū)間：一個(gè)是遞增區(qū)間，另一個(gè)是遞減區(qū)間。峰值實(shí)際上是這兩個(gè)區(qū)間的交界點(diǎn)。

假設(shè)我們隨機(jī)選擇一個(gè)點(diǎn)進(jìn)行比較，如果它比右側(cè)位置的值小，說明它在一個(gè)遞增的區(qū)間；反之，如果它比右側(cè)位置的值大，說明它在一個(gè)遞減的區(qū)間。

基于這個(gè)性質(zhì)，我們可以運(yùn)用二分算法。當(dāng) nums[mid] < nums[mid+1] 時(shí)，表示在一個(gè)遞增區(qū)間，峰值必定在 mid+1 及其之后的位置；而當(dāng) nums[mid] > nums[mid+1] 時(shí)，表示在一個(gè)遞減區(qū)間，峰值可能在 mid 或其之前的位置（需要注意，峰值有可能就是在 mid 位置）。

因此，我們更新 right = mid，而不需要進(jìn)行 -1 的操作。由于不需要 -1，當(dāng) left == right 時(shí)，如果已經(jīng)找到峰值，我們應(yīng)該如何退出循環(huán)呢？

這里可以進(jìn)行特殊處理，或者將循環(huán)條件改成 left < right。在某些情況下，模板并不是固定不變的，我們可以根據(jù)實(shí)際情況進(jìn)行調(diào)整。通過解決這道題，我們不僅學(xué)到了一些技巧，也積累了寶貴的經(jīng)驗(yàn)。

5.尋找旋轉(zhuǎn)排序數(shù)組中的最小值(難度??)

Leetcode鏈接：153.?尋找旋轉(zhuǎn)排序數(shù)組中的最小值

5.1題目描述：

這題的解題思路與前面一道問題相似，我們需要根據(jù)所給的條件找到一個(gè)可以進(jìn)行比較的參照物或者說參照系。讓我們來審視一下具體的代碼。

5.2代碼：

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size() - 1;int left = 0, right = n, mid = 0;while(left < right){mid = (left + right)/2;if(nums[mid] > nums[n]){left = mid + 1;}else if(nums[mid] < nums[n]){right = mid;}}return nums[left];}
};

考慮到題目給出的是一個(gè)經(jīng)過旋轉(zhuǎn)的升序數(shù)組，這使得數(shù)組不再是有序的，我們需要思考如何運(yùn)用二分法來解決這一問題。

觀察到，經(jīng)過旋轉(zhuǎn)的升序數(shù)組可以分為兩個(gè)遞增的區(qū)間，一個(gè)較大的區(qū)間和一個(gè)較小的區(qū)間。我們可以以區(qū)間的最大值作為參照物來進(jìn)行分析。

以最右邊的元素為例，它可能是小區(qū)間的最大值，也可能是大區(qū)間的最大值。如果它是大區(qū)間的最大值，這就意味著數(shù)組沒有經(jīng)過旋轉(zhuǎn)，因此我們可以先忽略這種特殊情況（這是一個(gè)解題的小技巧，特殊情況可以后續(xù)再處理）。

題目要求找到最小的元素，即小區(qū)間的最小值。因此，我們需要找到小區(qū)間，并在其中找到最小元素。具體操作如下：

• 當(dāng) nums[mid] > nums[n] 時(shí)，表示中間位置 mid 處于大區(qū)間，因此將 left 調(diào)整為 mid + 1；
• 當(dāng) nums[mid] < nums[n] 時(shí)，表示中間位置 mid 處于小區(qū)間，因此將 right 調(diào)整為 mid。注意，這里不能減1，因?yàn)槲覀円业闹翟谛^(qū)間內(nèi)，不能排除掉中間元素。
• 接著，考慮特殊情況，即當(dāng) nums[mid] < nums[n] 時(shí)，數(shù)組的最右元素 n 是大區(qū)間的最大值。如果我們讓 right = mid，會(huì)導(dǎo)致最終循環(huán)結(jié)束時(shí)出現(xiàn) left = right 的情況。為了避免這種情況，我們將循環(huán)的條件調(diào)整為 left < right。

這道題是二分法的一個(gè)變式，關(guān)鍵在于找到以何為參照系來確定區(qū)間的位置，一旦確定，后續(xù)的工作就變得相對容易。

6.點(diǎn)名（難度?）

Leetcode鏈接：LCR 173. 點(diǎn)名

6.1題目描述：

這道題我其實(shí)一開始也想不出來，選這道題的目的其實(shí)也是想說明，算法積累的重要性，見多識(shí)廣，才能思路開闊，臨危不亂。

6.2代碼：

class Solution 
{
public:int takeAttendance(vector<int>& records) {int n = records.size() - 1;int left = 0, right = n, mid = 0;while(left < right){mid = (left + right)/2;if(records[mid] == mid){left = mid + 1;}else{right = mid;}}if (records[right] == right) {return right+1;}return right;}
};

總結(jié)一下：

完成了這六道題目后，相信你對二分查找已經(jīng)得心應(yīng)手了～

接下來，繼續(xù)努力，迎接新的挑戰(zhàn)吧～

如果有一天覺得對二分有些生疏了，不妨回來再刷一遍，鞏固一下技能～

最后，祝愿你未來的刷題之路愉快順利～