這節課我們將重點介紹二分搜索算法，并且介紹一下貪婪算法。
二分搜索算法看似簡單，寫對很難，而且變形很多。所以最容易被拿來在面試中考察大家寫 code 的能力。本節課可以總結出解決二分搜索題目的常用套路。
貪婪算法雖然是一種比較直觀的算法，但是比較難的地方在于證明它的正確性。換句話說，有時候它會讓你誤以為得到的答案是正確的解，其實不然。
#### 二分搜索（Binary Search）
二分搜索（折半搜索）的 Wikipedia 定義：是一種在有序數組中查找某一特定元素的搜索算法。從定義可知，運用二分搜索的前提是數組必須是排好序的。另外，輸入并不一定是數組，也有可能是給定一個區間的起始和終止的位置。
**優點**：時間復雜度是 O(lgn)，非常高效。
因此也稱為對數搜索。
**缺點**：要求待查找的數組或者區間是排好序的。
對數組進行動態的刪除和插入操作并完成查找，平均復雜度會變為 O(n)。此時應當考慮采取自平衡的二叉查找樹：
* 在 O(nlogn) 的時間內用給定的數據構建出一棵二叉查找樹；
* 在 O(logn) 的時間里對目標數據進行搜索；
* 在 O(logn) 的時間里完成刪除和插入的操作。
因此，當輸入的數組或者區間是排好序的，同時又不會經常變動，而要求從里面找出一個滿足條件的元素的時候，二分搜索就是最好的選擇。
二分搜索一般化的解題思路如下。
1. 從已經排好序的數組或區間中取出中間位置的元素，判斷該元素是否滿足要搜索的條件，如果滿足，停止搜索，程序結束。
2. 如果正中間的元素不滿足條件，則從它兩邊的區域進行搜索。由于數組是排好序的，可以利用排除法，確定接下來應該從這兩個區間中的哪一個去搜索。
3. 通過判斷，如果發現真正要找的元素在左半區間的話，就繼續在左半區間里進行二分搜索。反之，就在右半區間里進行二分搜索。
**遞歸解法**
優點：簡潔；缺點：執行消耗大
例題：假設我們要從一個排好序的數組里 {1, 3, 4, 6, 7, 8, 10, 13, 14} 查看一下數字 7 是否在里面，如果在，返回它的下標，否則返回 -1。
**代碼實現**
遞歸寫法的代碼模板如下。
```
// 二分搜索函數的定義里，除了要指定數組 nums 和目標查找數 target 之外，還要指定查找區間的起點和終點位置，分別用 low 和 high 去表示。
int?binarySearch(int[]?nums,?int?target,?int?low,?int?high)?{
? ? ? ?// 為了避免無限循環，先判斷，如果起點位置大于終點位置，表明這是一個非法的區間，已經嘗試了所有的搜索區間還是沒能找到結果，返回 -1。
if?(low?>?high)?{
???? ? ?return?-1;
? ?}
? ?// 取正中間那個數的下標 middle。
? ?int?middle?=?low?+?(high?-?low)?/?2;
? ?
? ?// 判斷一下正中間的那個數是不是要找的目標數 target，是，就返回下標 middle。 ? ?
?? ?if?(nums[middle]?==?target)?{
???? ? ?return?middle;
? ?}
? ?
? ? // 如果發現目標數在左邊，就遞歸地從左半邊進行二分搜索。
? ?if?(target?<?nums[middle])?{
???? ? ?return?binarySearch(nums,?target,?low,?middle?-?1);
?? ? ?}?else?{
???? ? ?return?binarySearch(nums,?target,?middle?+?1,?high);
? ?}//否則從右半邊遞歸地進行二分搜索。
}
```
注意：
1. 在計算 middle 下標的時候，不能簡單地用 (low + hight) / 2，可能會導致溢出。
2. 在取左半邊以及右半邊的區間時，左半邊是 [low, middle - 1]，右半邊是 [middle + 1, high]，這是兩個閉區間。因為已經確定了 middle 那個點不是我們要找的，就沒有必要再把它加入到左、右半邊了。
3. 對于一個長度為奇數的數組，例如：{1, 2, 3, 4, 5}，按照 low + (high - low) / 2 來計算，middle 就是正中間的那個位置，對于一個長度為偶數的數組，例如 {1, 2, 3, 4}，middle 就是正中間靠左邊的一個位置。
**時間復雜度**
假設我們要對長度為 n 的數組進行二分搜索，T(n) 是執行時間函數，我們可以得到
```
T(n) = T(n/2) + 1
```
代入公式法得：a = 1，b = 2，f(n) = 1，因此：O(nlog(b)a) = O(n0) = 1 等于 O(f(n))，時間復雜度就是 O(nlog(b)alogn) = O(logn)。
**非遞歸解法**
**代碼實現**
非遞歸寫法的代碼模板如下。
```
int?binarySearch(int[]?nums,?int?target,?int?low,?int?high)?{
? ?//?在?while?循環里，判斷搜索的區間范圍是否有效
? ?while?(low?<=?high)?{
???? ? ?//?計算正中間的數的下標
???? ? ?int?middle?=?low?+?(high?-?low)?/?2;
????
????//?判斷正中間的那個數是不是要找的目標數?target。如果是，就返回下標?middle
????if?(nums[middle]?==?target)?{
???? ? ?return?middle;
????}
????
????//?如果發現目標數在左邊，調整搜索區間的終點為?middle?-?1；否則，調整搜索區間的起點為?middle?+?1
????if?(target?<?nums[middle])?{
???? ? ?high?=?middle?-?1;
???? ?}?else?{
? ? ? ?low?=?middle?+?1;
? ? ?}
? ?}
? ?//?如果超出了搜索區間，表明無法找到目標數，返回?-1??
? ?return?-1;
}
```
**核心步驟**
1. 確定搜索的范圍和區間
2. 取中間的數判斷是否滿足條件
3. 如果不滿足條件，判定應該往哪個半邊繼續進行搜索
二分搜索看起來簡單，但是?Programming Pearls?這本書的作者 Jon Bentley 提到，只有 10% 的程序員能正確地寫出二分搜索的代碼。面試題經常是經典二分搜索的變形，但萬變不離其中，需要把握好二分搜索的核心。
**例題分析一：找確定的邊界**
邊界分上邊界和下邊界，有時候也被成為右邊界和左邊界。確定的邊界指邊界的數值等于要找的目標數。
例題：LeetCode 第 34 題，在一個排好序的數組中找出某個數第一次出現和最后一次出現的下標位置。
示例：輸入的數組是：{5, 7, 7, 8, 8, 10}，目標數是 8，那么返回 {3, 4}，其中 3 是 8 第一次出現的下標位置，4 是 8 最后一次出現的下標位置。
**解題思路**
在二分搜索里，比較難的是判斷邏輯，對這道題來說，什么時候知道這個位置是不是 8 第一次以及最后出現的地方呢？
把第一次出現的地方叫下邊界（lower bound），把最后一次出現的地方叫上邊界（upper bound）。
那么成為 8 的下邊界的條件應該有兩個。
1. 該數必須是 8；
2. 該數的左邊一個數必須不是 8：
* 8 的左邊有數，那么該數必須小于 8；
* 8 的左邊沒有數，即 8 是數組的第一個數。
而成為 8 的上邊界的條件也應該有兩個。
1. 該數必須是 8；
2. 該數的右邊一個數必須不是 8：
* 8 的右邊有數，那么該數必須大于8；
* 8 的右邊沒有數，即 8 是數組的最后一個數。
**代碼實現**
用遞歸的方法來尋找下邊界，代碼如下。
```
int?searchLowerBound(int[]?nums,?int?target,?int?low,?int?high)?{
????if?(low?>?high)?{
????????return?-1;
????}
??
????int?middle?=?low?+?(high?-?low)?/?2;
????//判斷是否是下邊界時，先看看?middle?的數是否為?target，并判斷該數是否已為數組的第一個數，或者，它左邊的一個數是不是已經比它小，如果都滿足，即為下邊界。
????if?(nums[middle]?==?target?&&?(middle?==?0?||?nums[middle?-?1]?<?target))?{
????????return?middle;
????}
????if?(target?<=?nums[middle])?{
????????return?searchLowerBound(nums,?target,?low,?middle?-?1);
??????}?else?{
????????return?searchLowerBound(nums,?target,?middle?+?1,?high);
??????}?//不滿足，如果這個數等于?target，那么就得往左邊繼續查找。
}
```
其他的寫法都和經典的二分搜索的寫法相同，不再贅述。
查找上邊界的代碼如下。
```
int?searchUpperBound(int[]?nums,?int?target,?int?low,?int?high)?{
????if?(low?>?high)?{
????????return?-1;
????}
??
????int?middle?=?low?+?(high?-?low)?/?2;
????
????//判斷是否是上邊界時，先看看?middle?的數是否為?target，并判斷該數是否已為數組的最后一個數，或者，它右邊的數是不是比它大，如果都滿足，即為上邊界。????
????if?(nums[middle]?==?target?&&?(middle?==?nums.length?-?1?||?nums[middle?+?1]?>?target))?{
????????return?middle;
????}
????
????if?(target?<?nums[middle])?{
????????return?searchUpperBound(nums,?target,?low,?middle?-?1);
??????}?else?{
????????return?searchUpperBound(nums,?target,?middle?+?1,?high);
??????}?//不滿足時，需判斷搜索方向。
}
```
* [ ] 例題分析二：找模糊的邊界
二分搜索可以用來查找一些模糊的邊界。模糊的邊界指，邊界的值并不等于目標的值，而是大于或者小于目標的值。
例題：從數組 {-2, 0, 1, 4, 7, 9, 10} 中找到第一個大于 6 的數。
**解題思路**
在一個排好序的數組里，判斷一個數是不是第一個大于 6 的數，只要它滿足如下的條件：
1. 該數要大于 6；
2. 該數有可能是數組里的第一個數，或者它之前的一個數比 6 小。
只要滿足了上面的條件就是第一個大于 6 的數。
代碼實現
```
Integer?firstGreaterThan(int[]?nums,?int?target,?int?low,?int?high)?{
????if?(low?>?high)?{
????????return?null;
????}
??
????int?middle?=?low?+?(high?-?low)?/?2;
????
????//判斷?middle?指向的數是否為第一個比?target?大的數時，須同時滿足兩個條件：middle?這個數必須大于?target；middle?要么是第一個數，要么它之前的數小于或者等于?target。?
????if?(nums[middle]?>?target?&&?(middle?==?0?||?nums[middle?-?1]?<=?target))?{
????????return?middle;
????}
????if?(target?<?nums[middle])?{
????????return?firstGreaterThan(nums,?target,?low,?middle?-?1);
??????}?else?{
????????return?firstGreaterThan(nums,?target,?middle?+?1,?high);
??????}
}
```
對于這道題，當不滿足條件，而 middle 的數等于 target 的時候怎么辦？舉例說明，如果要求的是第一個大于 6 的數，而數組中有多個 6 挨在一起，而此時的 middle 指向其中的一個 6，程序必須得在右半邊搜索。
找模糊邊界的題，還有在給定數組里，找最后一個比目標數小的數。
舉例：在 {-2, 0, 1, 4, 7, 9, 10} 中，求最后一個比 6 小的數。
答案是 4，方法是類似的。
* [ ] 例題分析三：旋轉過的排序數組
二分搜索也能在經過旋轉了的排序數組中進行。
例題：LeetCode 第 33 題，給定一個經過旋轉了的排序數組，判斷一下某個數是否在里面。
示例：給定數組為 {4, 5, 6, 7, 0, 1, 2}，target 等于 0，答案是 4，即 0 所在的位置下標是 4。
解題思路
對于這道題，輸入數組不是完整排好序，還能運用二分搜索嗎？思路如下。
一開始，中位數是 7，并不是我們要找的 0，如何判斷往左邊還是右邊搜索呢？這個數組是經過旋轉的，即，從數組中的某個位置開始劃分，左邊和右邊都是排好序的。
如何判斷左邊是不是排好序的那個部分呢？只要比較 nums[low] 和 nums[middle]。nums[low] <= nums[middle] 時，能判定左邊這部分一定是排好序的，否則，右邊部分一定是排好序的。
為什么要判斷 nums[low] = nums[middle] 的情況呢？因為計算 middle 的公式是 int middle = low + (high - low) / 2。
當只有一個數的時候，low=high，middle=ow，同樣認為這一邊是排好序的。
判定某一邊是排好序的，有什么用處呢？能準確地判斷目標值是否在這個區間里。如果 nums[low] <= target && target < nums[middle]，則應該在這個區間里搜索目標值。反之，目標值肯定在另外一邊。
代碼實現
```
int?binarySearch(int[]?nums,?int?target,?int?low,?int?high)?{
????if?(low?>?high)?{
????????return?-1;
????}?//判斷是否已超出了搜索范圍，是則返回-1。
??
????int?middle?=?low?+?(high?-?low)?/?2;?//取中位數。
????if?(nums[middle]?==?target)?{
????????return?middle;
????}?//判斷中位數是否為要找的數
????if?(nums[low]?<=?nums[middle])?{?//判斷左半邊是不是排好序的。
????????if?(nums[low]?<=?target?&&?target?<?nums[middle])?{?//是，則判斷目標值是否在左半邊。
????????????return?binarySearch(nums,?target,?low,?middle?-?1);?//是，則在左半邊繼續進行二分搜索。
????????}
????????return?binarySearch(nums,?target,?middle?+?1,?high);?//否，在右半邊進行二分搜索。
??????}?else?{
????????if?(nums[middle]?<?target?&&?target?<=?nums[high])?{?//若右半邊是排好序的那一半，判斷目標值是否在右邊。
????????????return?binarySearch(nums,?target,?middle?+?1,?high);?//是，則在右半邊繼續進行二分搜索。
????????}
????????return?binarySearch(nums,?target,?low,?middle?-?1);?//否，在左半邊進行二分搜索。
????}
}
```
在決定在哪一邊進行二分搜索的時候，利用了旋轉數組的性質，這就是這道題的巧妙之處。
* [ ] 例題分析四：不定長的邊界
前面介紹的二分搜索的例題都給定了一個具體范圍或者區間，那么對于沒有給定明確區間的問題能不能運用二分搜索呢？
例題：有一段不知道具體長度的日志文件，里面記錄了每次登錄的時間戳，已知日志是按順序從頭到尾記錄的，沒有記錄日志的地方為空，要求當前日志的長度。
解題思路
可以把這個問題看成是不知道長度的數組，數組從頭開始記錄都是時間戳，到了某個位置就成為了空：{2019-01-14, 2019-01-17, … , 2019-08-04, …. , null, null, null ...}。
思路 1：順序遍歷該數組，一直遍歷下去，當發現第一個 null 的時候，就知道了日志的總數量。很顯然，這是很低效的辦法。
思路 2：借用二分搜索的思想，反著進行搜索。
一開始設置 low = 0，high = 1
只要 logs[high] 不為 null，high *= 2
當 logs[high] 為 null 的時候，可以在區間 [0, high] 進行普通的二分搜索
代碼實現
```
//?先通過getUpperBound函數不斷地去試探在什么位置會出現空的日志。
int?getUpperBound(String[]?logs,?int?high)?{
????if?(logs[high]?==?null)?{
????????return?high;
????}
????return?getUpperBound(logs,?high?*?2);
}
//?再運用二分搜索的方法去尋找日志的長度。
int?binarySearch(String[]?logs,?int?low,?int?high)?{
????if?(low?>?high)?{
????????return?-1;
????}
??
????int?middle?=?low?+?(high?-?low)?/?2;
??
????if?(logs[middle]?==?null?&&?logs[middle?-?1]?!=?null)?{
????????return?middle;
????}
??
????if?(logs[middle]?==?null)?{
????????return?binarySearch(logs,?low,?middle?-?1);
??????}?else?{
????????return?binarySearch(logs,?middle?+?1,?high);
????}
}
```
判斷是否是日志的結尾很簡單，只要當前的日志為空，而前一個日志不為空即可。
* [ ] 貪婪（Greedy）
貪婪算法的 Wikipedia 定義：是一種在每一步選中都采取在當前狀態下最好或最優的選擇，從而希望導致結果是最好或最優的算法。
優點：對于一些問題，非常直觀有效。
缺點：
* 并不是所有問題都能用它去解決；
* 得到的結果并一定不是正確的，因為這種算法容易過早地做出決定，從而沒有辦法達到最優解。
下面通過例題來加深對貪婪算法的認識。例題：0-1 背包問題，能不能運用貪婪算法去解決。
有三種策略：
* 選取價值最大的物品
* 選擇重量最輕的物品
* 選取價值/重量比最大的物品
策略 1：每次盡可能選擇價值最大的，行不通。舉例說明如下。
物品有：A B C
重量分別是：25, 10, 10
價值分別是：100，80，80
根據策略，首先選取物品 A，接下來就不能再去選其他物品，但是，如果選取 B 和 C，結果會更好。
策略 2：每次盡可能選擇輕的物品，行不通。舉例說明如下。
物品有：A B C
重量分別為：25, 10, 10
價值分別為：100, 5, 5
根據策略，首先選取物品 B 和 C，接下來就不能選 A，但是，如果選 A，價值更大。
策略 3：每次盡可能選價值/重量比最大的，行不通。舉例說明如下。
物品有：A B C
重量是：25, 10, 10
價值是：25, 10, 10
根據策略，三種物品的價值/重量比都是一樣，如果選 A，答案不對，應該選 B 和 C。
由上，貪婪算法總是做出在當前看來是最好的選擇。即，它不從整體的角度去考慮，僅僅對局部的最優解感興趣。因此，只有當那些局部最優策略能產生全局最優策略的時候，才能用貪婪算法。
**例題分析**
LeetCode 第 253 題，會議室II，給定一系列會議的起始時間和結束時間，求最少需要多少個會議室就可以讓這些會議順利召開。
**解題思路**
思路 1：暴力法。
* 把所有的會議組合找出來；
* 從最長的組合開始檢查，看看各個會議之間有沒有沖突；
* 直到發現一組會議沒有沖突，那么它就是答案。
很明顯，這樣的解法是非常沒有效率的。
思路 2：貪婪算法
* 會議按照起始時間順序進行；
* 要給新的即將開始的會議找會議室時，先看當前有無空會議室；
* 有則在空會議室開會，無則開設一間新會議室。
代碼實現
```
int?minMeetingRooms(Interval[]?intervals)?{
????if?(intervals?==?null?||?intervals.length?==?0)
????????return?0;
????
????//?將輸入的一系列會議按照會議的起始時間排序。
????Arrays.sort(intervals,?new?Comparator<Interval>()?{
????????public?int?compare(Interval?a,?Interval?b)?{?return?a.start?-?b.start;?}
????});
??
????//?用一個最小堆來維護目前開辟的所有會議室，最小堆里的會議室按照會議的結束時間排序。
????PriorityQueue<Interval>?heap?=?new?PriorityQueue<Interval>(intervals.length,?new?Comparator<Interval>()?{
????????public?int?compare(Interval?a,?Interval?b)?{?return?a.end?-?b.end;?}
????});
??
????//?讓第一個會議在第一個會議室里舉行。
????heap.offer(intervals[0]);
??
????for?(int?i?=?1;?i?<?intervals.length;?i++)?{
????????//?從第二個會議開始，對于每個會議，我們都從最小堆里取出一個會議室，那么這個會議室里的會議一定是最早結束的。
????????Interval?interval?=?heap.poll();
????
????????if?(intervals[i].start?>=?interval.end)?{
????????//?若當前要開的會議可以等會議室被騰出才開始，那么就可以重復利用這個會議室。
????????interval.end?=?intervals[i].end;
??????}?else?{
????????//?否則，開一個新的會議室。
????????heap.offer(intervals[i]);
????}
????
????//?把舊的會議室也放入到最小堆里。
????heap.offer(interval);
????}
????//?最小堆里的會議室個數就是要求的答案，即最少的會議個數。
????return?heap.size();
}
```
為什么貪婪算法能在這里成立？
每當遇到一個新的會議時，總是貪婪地從所有會議室里找出最先結束會議的那個。
為什么這樣可以產生最優的結果？
若選擇的會議室中會議未結束，則意味著需要開辟一個新會議室，這已經不是當前的最優解了
**建議**：貪婪算法考點在面試中相對于其他算法而言是比較輕的，大家只需要把常見的一些利用貪婪算法解題的題目多加練習即可。
#### 結語
這節課講解了二分搜索算法和貪婪算法。其中，二分搜索算法是重中之重，因為它看似簡單，但要寫對卻不那么容易。
建議：LeetCode 上對二分搜索算法和貪婪算法的相關題目都做了很好的篩選，大家要多加練習。
從下節課開始，我們將運用之前學到的數據結構和算法知識來解決一些高頻算法面試題以及難題。
