參考內(nèi)容：二分查找

二分查找其實(shí)是一個(gè)非常不好寫的問題。雖然二分查找的思想非常簡(jiǎn)單，但是實(shí)際操作起來的時(shí)候需要考慮一些邊界情況，導(dǎo)致常常不能one pass。

所以我專門結(jié)合b站的這個(gè)視頻中提出的模板結(jié)合Leetcode題目展開了專題練習(xí)

二分查找

寫了這些題目：

搜索插入位置，尋找峰值，在排序數(shù)組中查找元素的第一個(gè)位置和最后一個(gè)位置，搜索二維矩陣，搜索二維矩陣II，尋找重復(fù)數(shù)，較小的三數(shù)之和，最接近的二叉搜索樹，尋找右區(qū)間來鞏固我對(duì)于二叉查找的模板的理解。?

下面我首先將視頻中的要點(diǎn)進(jìn)行整理，然后逐題進(jìn)行復(fù)盤。

二分查找模板 + 細(xì)節(jié)問題的數(shù)學(xué)證明 &搜索插入位置

和我們一般見到的二分查找的模板有如下幾點(diǎn)不同：

1. left表示當(dāng)前指向的元素，及其左邊的元素都屬于藍(lán)色部分，right表示當(dāng)前指向的元素及其右邊的元素的都屬于紅色部分

初始化left = 1，right = N，即數(shù)組長(zhǎng)度。之所以要如此初始化，是為了符合模板中對(duì)于left和right的定義。

2. left和right每次最后都被賦值為mid。這是因?yàn)閷eft = mid + 1或者是將 right = mid + 1，我們不容易判斷更新之后的left是屬于紅色還是藍(lán)色。

以上兩點(diǎn)是最顯著的區(qū)別，其余的數(shù)學(xué)證明大家可以參考一下原視頻。

當(dāng)循環(huán)結(jié)束時(shí)，left和right會(huì)終止在各自的顏色的位置，如圖所示：

因此，當(dāng)前最要緊的問題就是如何定義

相當(dāng)于說是，只需要考慮什么元素需要加入藍(lán)色部分，其他的元素全部都加入紅色部分即可。

對(duì)于這個(gè)問題的說明 我們就使用搜索插入位置這道題來舉例：

通過觀察實(shí)例輸入和輸出，我們可以發(fā)現(xiàn)，最終的結(jié)果表示的下標(biāo)包括了大于等于target的數(shù)字。因此我們可以將isBlue定義為小于nums的數(shù)字，代碼如下：

尋找峰值

關(guān)于這道題，首先需要考慮是否能使用二分查找？

首先我們假設(shè)數(shù)組中存在峰值，如果一個(gè)下標(biāo)i對(duì)應(yīng)的元素及其左右元素滿足如下關(guān)系：

num[i] < nums[i+1] && nums[i] ?>?nums[i-1] 說明峰值在其右邊；

num[i] >?nums[i+1] && nums[i] <?nums[i-1] 說明峰值在其左邊；

num[i] < nums[i+1] && nums[i] ??<?nums[i-1] 說明在谷底，下一步往左邊和右邊都可以

所以可以認(rèn)為使用二分查找，一次可以忽略左邊或者右邊的數(shù)字，加快搜索

為什么存在峰值

首先，示例以及題目中沒有說明不存在峰值應(yīng)該返回什么元素，所以一定存在。其實(shí)也可推導(dǎo)。

假設(shè)數(shù)組中存在一個(gè)元素，這個(gè)元素就是峰值；

假設(shè)數(shù)組中存在兩個(gè)元素，若左邊的元素大于右邊的元素，左邊的元素就是峰值；反之則右邊的元素是峰值。存在更多元素的情況就是兩個(gè)元素的情況的展開

既然如此，我們需要考慮isBlue的實(shí)現(xiàn)。

對(duì)于一個(gè)元素，如果這個(gè)元素小于右邊大于左邊，則可以放到藍(lán)色區(qū)域，那么，最后一個(gè)放入藍(lán)色區(qū)域的元素的下一個(gè)元素就是峰值。

另外題目中還說明了，不存在重復(fù)元素的情況，上述代碼中等號(hào)可以去掉。

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

這題思路沒有特別之處，將小于target的值歸到藍(lán)色區(qū)間，返回最后的right就可以。二分查找的模板存在一個(gè)問題，如果數(shù)組元素值都小于target，那么right的值為N；如果數(shù)組元素的值都大于target，返回值為0。

在上面的例子中，因?yàn)橐业骄唧w的元素的下標(biāo)，所以需要檢查最后返回right對(duì)應(yīng)的元素是不是Target，并且還需要先考慮返回的right有沒有數(shù)組越界。????

搜索二維矩陣

根據(jù)題意不難理解，這題就是將一個(gè)很長(zhǎng)的數(shù)組切成一些小段放到二維數(shù)組中。其實(shí)也是按照一位數(shù)組的模板來做就完事了。m*n就是數(shù)組總長(zhǎng)度，m*n / n表示i m*n%n 表示j：

搜索二維矩陣II

這道題和上面的有所區(qū)別，因?yàn)槊恳恍械淖詈笠粋€(gè)元素不一定小于下一行的第一個(gè)元素，所以不能展開成一個(gè)長(zhǎng)一位數(shù)組。但是這種矩陣有一種特性，從右上角開始，向左邊走的元素小于他，下面的元素大于他。這樣滿足一種二分特性。

對(duì)于Target=5而言，因?yàn)?5 大于 5，向左走；11 大于5向左，7大于5向左；4小于5 向下找到了；如果沒找到就回走到數(shù)組矩陣外面，返回false即可。

這道題劃分紅藍(lán)區(qū)間不容易設(shè)計(jì)，直接使用最簡(jiǎn)單的即可。

較小的三數(shù)之和

題目要求找到三個(gè)數(shù)，并且讓這三個(gè)數(shù)之和小于target。我們可以將原數(shù)組進(jìn)行排序，找到其中的兩個(gè)數(shù)，他們的下標(biāo)分別記作i,j，然后找一個(gè)下標(biāo)為k的數(shù)，滿足nums[k] <?target-nums[i]-nums[j]，如圖所示，藍(lán)色的部分就是找到的區(qū)間.

通過圖我們可以發(fā)現(xiàn)，其實(shí)也不會(huì)出現(xiàn)重復(fù)的問題。比如當(dāng)j指向下標(biāo)為2的元素，也就是1時(shí)，k也找不到下標(biāo)為3的元素，也就是3.

具體代碼如下：

尋找右區(qū)間

這道題要求找當(dāng)前的區(qū)間的右區(qū)間，如果找不到就-1，找得到就下標(biāo)。????其實(shí)做了這么多關(guān)于區(qū)間的題，不論是使用貪心的原則，合并區(qū)間也好，還是其他的方法也罷，一上來的第一個(gè)思路就是將區(qū)間元素按照區(qū)間中的start大小進(jìn)行排序。我們想想這個(gè)排序的思路是否可以運(yùn)用到這道題。

對(duì)于圖中的這個(gè)例子而言，因?yàn)閑nd一定大于start，通過start進(jìn)行排序之后的元組可以通過檢查當(dāng)前mid指向的元素是否為[1,4]的右區(qū)間。我們通過設(shè)計(jì)不是右區(qū)間的在藍(lán)色區(qū)域，第一個(gè)是右區(qū)間的在紅色區(qū)域就滿足了題目的最小化start的要求。

同時(shí)這道題其實(shí)有個(gè)case很智障，[1,1]也是自己的右區(qū)間，所以需要額外判斷當(dāng)start=end的情況。

具體代碼如下：

通過我們的整理我們可以看到，視頻中的這個(gè)模板非常適合完成對(duì)于給定的數(shù)組搜索其中元素的任務(wù)，但是對(duì)于沒有給定數(shù)組的情況，或者不容易構(gòu)造數(shù)組的情況，下面還有一些通用的技巧：

尋找重復(fù)數(shù)

這道題中，給出長(zhǎng)度為n+1的數(shù)組，但是數(shù)組中有一個(gè)存在元素i，i屬于[1,n]存在一個(gè)重復(fù)值。我們可以有這樣的一個(gè)思路，我們?cè)O(shè)計(jì)left,right和mid指針，我們?cè)陬}目給定nums數(shù)組中，猜[left,mid]框定的區(qū)間內(nèi)，nums中的元素出現(xiàn)的次數(shù)。如果在nums中出現(xiàn)的次數(shù)大于mid-left+1，即區(qū)間長(zhǎng)度，說明存在重復(fù)元素。如果沒有出現(xiàn)重復(fù)元素說明當(dāng)前[left,mid]區(qū)間不對(duì)，我們轉(zhuǎn)到[mid+1,right]子區(qū)間中嘗試。

具體代碼如下：

此外，如果要驗(yàn)證自己的代碼是否正確可以使用最基本的一些Case進(jìn)行嘗試：

1. 數(shù)組長(zhǎng)度為2時(shí)數(shù)組為{1,1}，返回left會(huì)返回1

2. 數(shù)組長(zhǎng)度為3時(shí)，排序后的數(shù)組可能為{1,1,2}或者是{1,2,2}，left=1，right=2，第一次的mid等于1。對(duì)于{1,1,2}，[1,1]區(qū)間內(nèi)的cnt是2，right = mid,退出循環(huán)，left=1，并且作為返回值；對(duì)于{1,2,2},[1,1]區(qū)間的cnt為1，cnt等于區(qū)間長(zhǎng)度，left = mid + 1，退出循環(huán)，返回left=2. 這個(gè)例子也說明當(dāng)cnt等于區(qū)間長(zhǎng)度的時(shí)候left=mid+1.

最接近的二叉搜索樹

二叉搜索樹可以通過成中序遍歷形成一個(gè)有序數(shù)組，然后二分查找是可以的，這樣時(shí)間空間復(fù)雜度都很高，沒必要。

如果target小于當(dāng)前的節(jié)點(diǎn)，那么接近這個(gè)數(shù)的節(jié)點(diǎn)肯定在左子樹（往右邊走越來越大，而且有右子樹的最小值肯定大于當(dāng)前節(jié)點(diǎn)）；反之如果大于，找右子樹。終止的節(jié)點(diǎn)肯定在葉子節(jié)點(diǎn)上，同時(shí)在遍歷的過程記錄一個(gè)最小的距離的值。

具體代碼如下：