# 第一期講義-二分法
# 二分查找
二分查找又稱`折半搜索算法`。 狹義地來講,二分查找是一種在有序數組查找某一特定元素的搜索算法。這同時也是大多數人所知道的一種說法。實際上, 廣義的二分查找是將問題的規模縮小到原有的一半。類似的,三分法就是將問題規模縮小為原來的 1/3。
本文給大家帶來的內容則是`狹義地二分查找`,如果想了解其他廣義上的二分查找可以查看我之前寫的一篇博文 [從老鼠試毒問題來看二分法](https://lucifer.ren/blog/2019/12/11/laoshushidu/)
> 盡管二分查找的基本思想相對簡單,但細節可以令人難以招架 ... — 高德納
當喬恩·本特利將二分搜索問題布置給專業編程課的學生時,百分之 90 的學生在花費數小時后還是無法給出正確的解答,主要因為這些錯誤程序在面對邊界值的時候無法運行,或返回錯誤結果。1988 年開展的一項研究顯示,20 本教科書里只有 5 本正確實現了二分搜索。不僅如此,本特利自己 1986 年出版的《編程珠璣》一書中的二分搜索算法存在整數溢出的問題,二十多年來無人發現。Java 語言的庫所實現的二分搜索算法中同樣的溢出問題存在了九年多才被修復。
可見二分查找并不簡單, 本文就試圖帶你走近 ta,明白 ta 的底層邏輯,并提供模板幫助大家寫書 bug free 的二分查找代碼。
大家可以看完講義結合 [LeetCode Book 二分查找練習一下](https://leetcode-cn.com/leetbook/read/binary-search)
## 問題定義
給定一個由數字組成的有序數組 nums,并給你一個數字 target。問 nums 中是否存在 target。如果存在, 則返回其在 nums 中的索引。如果不存在,則返回 - 1。
這是二分查找中最簡單的一種形式。當然二分查找也有很多的變形,這也是二分查找容易出錯,難以掌握的原因。
常見變體有:
- 如果存在多個滿足條件的元素,返回最左邊滿足條件的索引。
- 如果存在多個滿足條件的元素,返回最右邊滿足條件的索引。
- 數組不是整體有序的。 比如先升序再降序,或者先降序再升序。
- 將一維數組變成二維數組。
- 。。。
接下來,我們逐個進行查看。
## 前提
- 數組是有序的(如果無序,我們也可以考慮排序,不過要注意排序的復雜度)
## 術語
二分查找中使用的術語:
- target —— 要查找的值
- index —— 當前位置
- l 和 r —— 左右指針
- mid —— 左右指針的中點,用來確定我們應該向左查找還是向右查找的索引
## 常見題型
### 查找一個數
算法描述:
- 先從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結束;
- 如果目標元素大于中間元素,則在數組大于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。
- 如果目標元素小于中間元素,則在數組小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。
- 如果在某一步驟數組為空,則代表找不到。
**復雜度分析**
- 平均時間復雜度: O(logN)O(logN)O(logN)
- 最壞時間復雜度: O(logN)O(logN)O(logN)
- 最優時間復雜度: O(1)O(1)O(1)
- 空間復雜度
- 迭代: O(1)O(1)O(1)
- 遞歸: O(logN)O(logN)O(logN)(無尾調用消除)
> 后面的復雜度也是類似的,不再贅述。
這種搜索算法每一次比較都使搜索范圍縮小一半,是典型的二分查找。
這個是二分查找中最簡答的一種類型了,我們先來搞定它。 我們來一個具體的例子, 這樣方便大家增加代入感。假設 nums 為 `[1,3,4,6,7,8,10,13,14]`, target 為 4·。
- 剛開始數組中間的元素為 7
- 7 > 4 ,由于 7 右邊的數字都大于 7 ,因此不可能是答案。我們將范圍縮寫到了 7 的左側。
- 此時中間元素為 3
- 3 < 4,由于 3 左邊的數字都小于 3 ,因此不可能是答案。我們將范圍縮寫到了 3 的右側。
- 此時中間元素為 4,正好是我們要找的,返回其索引 2 即可。
如何將上面的算法轉換為容易理解的可執行代碼呢?就算是這樣一個簡簡單單,樸實無華的二分查找, 不同的人寫出來的差別也是很大的。 如果沒有一個思維框架指導你,那么你在不同的時間可能會寫出差異很大的代碼。這樣的話,你犯錯的幾率會大大增加。
這里給大家介紹一個我經常使用的思維框架和代碼模板。
#### 思維框架
**首先定義搜索區間為 \[left, right\],注意是左右都閉合,之后會用到這個點**
> 你可以定義別的搜索區間形式,不過后面的代碼也相應要調整,感興趣的可以試試別的搜索區間。
- 由于定義的搜索區間為 \[left, right\],因此當 left <= right 的時候,搜索區間都不為空,此時我們都需要繼續搜索。 也就是說終止搜索條件應該為 left <= right。
> 舉個例子容易明白一點。 比如對于區間 \[4,4\],其包含了一個元素 4,因此搜索區間不為空,需要繼續搜索(試想 4 恰好是我們要找的 target,如果不繼續搜索, 會錯過正確答案)。而當搜索區間為 \[left, right) 的時候,同樣對于 \[4,4\],這個時候搜索區間卻是空的,因為這樣的一個區間不存在任何數字·。
- 循環體內,我們不斷計算 mid ,并將 nums\[mid\] 與 目標值比對。
- 如果 nums\[mid\] 等于目標值, 則提前返回 mid(只需要找到一個滿足條件的即可)
- 如果 nums\[mid\] 小于目標值, 說明目標值在 mid 右側,這個時候搜索區間可縮小為 \[mid + 1, right\] (mid 以及 mid 左側的數字被我們排除在外)
- 如果 nums\[mid\] 大于目標值, 說明目標值在 mid 左側,這個時候搜索區間可縮小為 \[left, mid - 1\] (mid 以及 mid 右側的數字被我們排除在外)
- 循環結束都沒有找到,則說明找不到,返回 -1 表示未找到。
#### 代碼模板
##### Java
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{
<span class="hljs-title">// 左右都閉合的區間 [l, r]</span>
<span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>;
<span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span>(left <= right) {
<span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>;
<span class="hljs-keyword">if</span>(nums[mid] == target)
<span class="hljs-keyword">return</span> mid;
<span class="hljs-keyword">if</span> (nums[mid] < target)
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] > target)
<span class="hljs-title">// 搜索區間變為 [left, mid - 1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>;
}
```
```
##### Python
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(nums, target)</span>:</span>
<span class="hljs-title"># 左右都閉合的區間 [l, r]</span>
l, r = <span class="hljs-params">0</span>, len(nums) - <span class="hljs-params">1</span>
<span class="hljs-keyword">while</span> l <= r:
mid = (left + right) >> <span class="hljs-params">1</span>
<span class="hljs-keyword">if</span> nums[mid] == target: <span class="hljs-keyword">return</span> mid
<span class="hljs-title"># 搜索區間變為 [mid+1, right]</span>
<span class="hljs-keyword">if</span> nums[mid] < target: l = mid + <span class="hljs-params">1</span>
<span class="hljs-title"># 搜索區間變為 [left, mid - 1]</span>
<span class="hljs-keyword">if</span> nums[mid] > target: r = mid - <span class="hljs-params">1</span>
<span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>
```
```
##### JavaScript
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">binarySearch</span>(<span class="hljs-params">nums, target</span>) </span>{
<span class="hljs-keyword">let</span> left = <span class="hljs-params">0</span>;
<span class="hljs-keyword">let</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span> (left <= right) {
<span class="hljs-keyword">const</span> mid = <span class="hljs-params">Math</span>.floor(left + (right - left) / <span class="hljs-params">2</span>);
<span class="hljs-keyword">if</span> (nums[mid] == target) <span class="hljs-keyword">return</span> mid;
<span class="hljs-keyword">if</span> (nums[mid] < target)
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] > target)
<span class="hljs-title">// 搜索區間變為 [left, mid - 1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>;
}
```
```
##### C++
暫時空缺,歡迎 [PR](https://github.com/leetcode-pp/leetcode-cheat/pulls)
```
<pre class="calibre18">```
```
```
### 尋找最左邊的滿足條件的值
和`查找一個數`類似, 我們仍然套用`查找一個數`的思維框架和代碼模板。
#### 思維框架
- 首先定義搜索區間為 \[left, right\],注意是左右都閉合,之后會用到這個點。
- 終止搜索條件為 left <= right。
- 循環體內,我們不斷計算 mid ,并將 nums\[mid\] 與 目標值比對。
- 如果 nums\[mid\] 等于目標值, 則收縮右邊界,我們找到了一個備胎,繼續看看左邊還有沒有了(**注意這里不一樣**)
- 如果 nums\[mid\] 小于目標值, 說明目標值在 mid 右側,這個時候搜索區間可縮小為 \[mid + 1, right\]
- 如果 nums\[mid\] 大于目標值, 說明目標值在 mid 左側,這個時候搜索區間可縮小為 \[left, mid - 1\]
- 由于不會提前返回,因此我們需要檢查最終的 left,看 nums\[left\]是否等于 target。
- 如果不等于 target,或者 left 出了右邊邊界了,說明至死都沒有找到一個備胎,則返回 -1.
- 否則返回 left 即可,備胎轉正。
#### 代碼模板
> 實際上 nums\[mid\] > target 和 nums\[mid\] == target 是可以合并的。我這里為了清晰,就沒有合并,大家熟悉之后合并起來即可。
##### Java
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearchLeft</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{
<span class="hljs-title">// 搜索區間為 [left, right]</span>
<span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>;
<span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span> (left <= right) {
<span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>;
<span class="hljs-keyword">if</span> (nums[mid] < target) {
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">if</span> (nums[mid] > target) {
<span class="hljs-title">// 搜索區間變為 [left, mid-1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">if</span> (nums[mid] == target) {
<span class="hljs-title">// 收縮右邊界</span>
right = mid - <span class="hljs-params">1</span>;
}
}
<span class="hljs-title">// 檢查是否越界</span>
<span class="hljs-keyword">if</span> (left >= nums.length || nums[left] != target)
<span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>;
<span class="hljs-keyword">return</span> left;
}
```
```
##### Python
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">binarySearchLeft</span><span class="hljs-params">(nums, target)</span>:</span>
<span class="hljs-title"># 左右都閉合的區間 [l, r]</span>
l, r = <span class="hljs-params">0</span>, len(nums) - <span class="hljs-params">1</span>
<span class="hljs-keyword">while</span> l <= r:
mid = (l + r) >> <span class="hljs-params">1</span>
<span class="hljs-keyword">if</span> nums[mid] == target:
<span class="hljs-title"># 收縮右邊界</span>
r = mid - <span class="hljs-params">1</span>;
<span class="hljs-title"># 搜索區間變為 [mid+1, right]</span>
<span class="hljs-keyword">if</span> nums[mid] < target: l = mid + <span class="hljs-params">1</span>
<span class="hljs-title"># 搜索區間變為 [left, mid - 1]</span>
<span class="hljs-keyword">if</span> nums[mid] > target: r = mid - <span class="hljs-params">1</span>
<span class="hljs-keyword">if</span> l >= len(nums) <span class="hljs-keyword">or</span> nums[l] != target: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>
<span class="hljs-keyword">return</span> l
```
```
##### JavaScript
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">binarySearchLeft</span>(<span class="hljs-params">nums, target</span>) </span>{
<span class="hljs-keyword">let</span> left = <span class="hljs-params">0</span>;
<span class="hljs-keyword">let</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span> (left <= right) {
<span class="hljs-keyword">const</span> mid = <span class="hljs-params">Math</span>.floor(left + (right - left) / <span class="hljs-params">2</span>);
<span class="hljs-keyword">if</span> (nums[mid] == target)
<span class="hljs-title">// 收縮右邊界</span>
right = mid - <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] < target)
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] > target)
<span class="hljs-title">// 搜索區間變為 [left, mid - 1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-title">// 檢查是否越界</span>
<span class="hljs-keyword">if</span> (left >= nums.length || nums[left] != target) <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>;
<span class="hljs-keyword">return</span> left;
}
```
```
##### C++
暫時空缺,歡迎 [PR](https://github.com/leetcode-pp/leetcode-cheat/pulls)
```
<pre class="calibre18">```
```
```
### 尋找最右邊的滿足條件的值
和`查找一個數`類似, 我們仍然套用`查找一個數`的思維框架和代碼模板。
> 有沒有感受到框架和模板的力量?
#### 思維框架
- 首先定義搜索區間為 \[left, right\],注意是左右都閉合,之后會用到這個點。
> 你可以定義別的搜索區間形式,不過后面的代碼也相應要調整,感興趣的可以試試別的搜索區間。
- 由于我們定義的搜索區間為 \[left, right\],因此當 left <= right 的時候,搜索區間都不為空。 也就是說我們的終止搜索條件為 left <= right。
> 舉個例子容易明白一點。 比如對于區間 \[4,4\],其包含了一個元素 4,因此搜索區間不為空。而當搜索區間為 \[left, right) 的時候,同樣對于 \[4,4\],這個時候搜索區間卻是空的。
- 循環體內,我們不斷計算 mid ,并將 nums\[mid\] 與 目標值比對。
- 如果 nums\[mid\] 等于目標值, 則收縮左邊界,我們找到了一個備胎,繼續看看右邊還有沒有了
- 如果 nums\[mid\] 小于目標值, 說明目標值在 mid 右側,這個時候搜索區間可縮小為 \[mid + 1, right\]
- 如果 nums\[mid\] 大于目標值, 說明目標值在 mid 左側,這個時候搜索區間可縮小為 \[left, mid - 1\]
- 由于不會提前返回,因此我們需要檢查最終的 right,看 nums\[right\]是否等于 target。
- 如果不等于 target,或者 right 出了左邊邊界了,說明至死都沒有找到一個備胎,則返回 -1.
- 否則返回 right 即可,備胎轉正。
#### 代碼模板
> 實際上 nums\[mid\] < target 和 nums\[mid\] == target 是可以合并的。我這里為了清晰,就沒有合并,大家熟悉之后合并起來即可。
##### Java
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearchRight</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{
<span class="hljs-title">// 搜索區間為 [left, right]</span>
<span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>
<span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span> (left <= right) {
<span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>;
<span class="hljs-keyword">if</span> (nums[mid] < target) {
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">if</span> (nums[mid] > target) {
<span class="hljs-title">// 搜索區間變為 [left, mid-1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-keyword">if</span> (nums[mid] == target) {
<span class="hljs-title">// 收縮左邊界</span>
left = mid + <span class="hljs-params">1</span>;
}
}
<span class="hljs-title">// 檢查是否越界</span>
<span class="hljs-keyword">if</span> (right < <span class="hljs-params">0</span> || nums[right] != target)
<span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>;
<span class="hljs-keyword">return</span> right;
}
```
```
##### Python
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">binarySearchRight</span><span class="hljs-params">(nums, target)</span>:</span>
<span class="hljs-title"># 左右都閉合的區間 [l, r]</span>
l, r = <span class="hljs-params">0</span>, len(nums) - <span class="hljs-params">1</span>
<span class="hljs-keyword">while</span> l <= r:
mid = (l + r) >> <span class="hljs-params">1</span>
<span class="hljs-keyword">if</span> nums[mid] == target:
<span class="hljs-title"># 收縮左邊界</span>
l = mid + <span class="hljs-params">1</span>;
<span class="hljs-title"># 搜索區間變為 [mid+1, right]</span>
<span class="hljs-keyword">if</span> nums[mid] < target: l = mid + <span class="hljs-params">1</span>
<span class="hljs-title"># 搜索區間變為 [left, mid - 1]</span>
<span class="hljs-keyword">if</span> nums[mid] > target: r = mid - <span class="hljs-params">1</span>
<span class="hljs-keyword">if</span> r < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> nums[r] != target: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>
<span class="hljs-keyword">return</span> r
```
```
##### JavaScript
```
<pre class="calibre18">```
<span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">binarySearchRight</span>(<span class="hljs-params">nums, target</span>) </span>{
<span class="hljs-keyword">let</span> left = <span class="hljs-params">0</span>;
<span class="hljs-keyword">let</span> right = nums.length - <span class="hljs-params">1</span>;
<span class="hljs-keyword">while</span> (left <= right) {
<span class="hljs-keyword">const</span> mid = <span class="hljs-params">Math</span>.floor(left + (right - left) / <span class="hljs-params">2</span>);
<span class="hljs-keyword">if</span> (nums[mid] == target)
<span class="hljs-title">// 收縮左邊界</span>
left = mid + <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] < target)
<span class="hljs-title">// 搜索區間變為 [mid+1, right]</span>
left = mid + <span class="hljs-params">1</span>;
<span class="hljs-keyword">if</span> (nums[mid] > target)
<span class="hljs-title">// 搜索區間變為 [left, mid - 1]</span>
right = mid - <span class="hljs-params">1</span>;
}
<span class="hljs-title">// 檢查是否越界</span>
<span class="hljs-keyword">if</span> (right < <span class="hljs-params">0</span> || nums[right] != target) <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>;
<span class="hljs-keyword">return</span> right;
}
```
```
##### C++
暫時空缺,歡迎 [PR](https://github.com/leetcode-pp/leetcode-cheat/pulls)
```
<pre class="calibre18">```
```
```
### 局部有序(先降后升或先升后降)
LeetCode 有原題 [33. 搜索旋轉排序數組](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) 和 [81. 搜索旋轉排序數組 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/), 我們直接拿過來講解好了。
其中 81 題是在 33 題的基礎上增加了`包含重復元素`的可能,實際上 33 題的進階就是 81 題。通過這道題,大家可以感受到”包含重復與否對我們算法的影響“。 我們直接上最復雜的 81 題,這個會了,可以直接 AC 第 33 題。
#### 81. 搜索旋轉排序數組 II
##### 題目描述
```
<pre class="calibre18">```
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如,數組 [0,0,1,2,2,5,6] 可能變為 [2,5,6,0,0,1,2] )。
編寫一個函數來判斷給定的目標值是否存在于數組中。若存在返回 true,否則返回 false。
示例 1:
輸入: nums = [2,5,6,0,0,1,2], target = 0
輸出: true
示例 2:
輸入: nums = [2,5,6,0,0,1,2], target = 3
輸出: false
進階:
這是 搜索旋轉排序數組 的延伸題目,本題中的 nums 可能包含重復元素。
這會影響到程序的時間復雜度嗎?會有怎樣的影響,為什么?
```
```
##### 思路
這是一個我在網上看到的前端頭條技術終面的一個算法題。我們先不考慮重復元素。
題目要求時間復雜度為 logn,因此基本就是二分法了。 這道題目不是直接的有序數組,不然就是 easy 了。
首先要知道,我們隨便選擇一個點,將數組分為前后兩部分,其中一部分一定是有序的。
具體步驟:
- 我們可以先找出 mid,然后根據 mid 來判斷,mid 是在有序的部分還是無序的部分
假如 mid 小于 start,則 mid 一定在右邊有序部分。 假如 mid 大于 start,則 mid 一定在左邊有序部分。
> 注意我沒有考慮等號,之后我會講。
- 然后我們繼續判斷 target 在哪一部分, 我們就可以舍棄另一部分了
我們只需要比較 target 和有序部分的邊界關系就行了。 比如 mid 在右側有序部分,即\[mid, end\] 那么我們只需要判斷 target >= mid && target <= end 就能知道 target 在右側有序部分,我們就 可以舍棄左邊部分了(start = mid + 1), 反之亦然。
我們以(\[6,7,8,1,2,3,4,5\], 4)為例講解一下:


接下來,我們考慮重復元素的問題。就會發生 nums\[mid\] == nums\[start\] 了,比如 30333 。這個時候,可以選擇 l 右移一位。有的同學會擔心”會不會錯失目標元素?“。其實這個擔心是多余的,前面我們已經介紹了”搜索區間“。由于搜索區間同時包含 l 和 mid ,因此去除一個 l ,我們還有 mid。假如 3 是我們要找的元素, 這樣進行下去絕對不會錯過,而是收縮”搜索區間“到一個元素 3 ,我們就可以心安理得地返回 3 了。
##### 代碼(Python)
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, nums, target)</span>:</span>
l, r = <span class="hljs-params">0</span>, len(nums)<span class="hljs-params">-1</span>
<span class="hljs-keyword">while</span> l <= r:
mid = l + (r-l)//<span class="hljs-params">2</span>
<span class="hljs-keyword">if</span> nums[mid] == target:
<span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
<span class="hljs-keyword">while</span> l < mid <span class="hljs-keyword">and</span> nums[l] == nums[mid]: <span class="hljs-title"># tricky part</span>
l += <span class="hljs-params">1</span>
<span class="hljs-title"># the first half is ordered</span>
<span class="hljs-keyword">if</span> nums[l] <= nums[mid]:
<span class="hljs-title"># target is in the first half</span>
<span class="hljs-keyword">if</span> nums[l] <= target < nums[mid]:
r = mid - <span class="hljs-params">1</span>
<span class="hljs-keyword">else</span>:
l = mid + <span class="hljs-params">1</span>
<span class="hljs-title"># the second half is ordered</span>
<span class="hljs-keyword">else</span>:
<span class="hljs-title"># target is in the second half</span>
<span class="hljs-keyword">if</span> nums[mid] < target <= nums[r]:
l = mid + <span class="hljs-params">1</span>
<span class="hljs-keyword">else</span>:
r = mid - <span class="hljs-params">1</span>
<span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
```
```
**復雜度分析**
- 時間復雜度:O(logN)O(log N)O(logN)
- 空間復雜度:O(1)O(1)O(1)
### 二維數組
二維數組的二分查找和一維沒有本質區別, 我們通過兩個題來進行說明。
#### 74. 搜索二維矩陣
##### 題目地址
<https://leetcode-cn.com/problems/search-a-2d-matrix/>
##### 題目描述
```
<pre class="calibre18">```
編寫一個高效的算法來判斷 m x n 矩陣中,是否存在一個目標值。該矩陣具有如下特性:
每行中的整數從左到右按升序排列。
每行的第一個整數大于前一行的最后一個整數。
示例 1:
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
輸出: true
示例 2:
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
輸出: false
```
```
##### 思路
簡單來說就是將一個一維有序數組切成若干長度相同的段,然后將這些段拼接成一個二維數組。你的任務就是在這個拼接成的二維數組中找到 target。
需要注意的是,數組是不存在重復元素的。
> 如果有重復元素,我們該怎么辦?
算法:
- 選擇矩陣左下角作為起始元素 Q
- 如果 Q > target,右方和下方的元素沒有必要看了(相對于一維數組的右邊元素)
- 如果 Q < target,左方和上方的元素沒有必要看了(相對于一維數組的左邊元素)
- 如果 Q == target ,直接 返回 True
- 交回了都找不到,返回 False
##### 代碼(Python)
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">searchMatrix</span><span class="hljs-params">(self, matrix: List[List[int]], target: int)</span> -> bool:</span>
m = len(matrix)
<span class="hljs-keyword">if</span> m == <span class="hljs-params">0</span>:
<span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
n = len(matrix[<span class="hljs-params">0</span>])
x = m - <span class="hljs-params">1</span>
y = <span class="hljs-params">0</span>
<span class="hljs-keyword">while</span> x >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> y < n:
<span class="hljs-keyword">if</span> matrix[x][y] > target:
x -= <span class="hljs-params">1</span>
<span class="hljs-keyword">elif</span> matrix[x][y] < target:
y += <span class="hljs-params">1</span>
<span class="hljs-keyword">else</span>:
<span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
<span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
```
```
**復雜度分析**
- 時間復雜度:最壞的情況是只有一行或者只有一列,此時時間復雜度為 O(M?N)O(M \* N)O(M?N)。更多的情況下時間復雜度為 O(M+N)O(M + N)O(M+N)
- 空間復雜度:O(1)O(1)O(1)
力扣 [240. 搜索二維矩陣 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/) 發生了一點變化,不再是`每行的第一個整數大于前一行的最后一個整數`,而是 `每列的元素從上到下升序排列`。我們仍然可以選擇左下進行二分。
### 尋找最值(改進的二分)
上面全部都是找到給定值,這次我們試圖尋找最值(最小或者最大)。我們以最小為例,講解一下這種題如何切入。
##### 153. 尋找旋轉排序數組中的最小值
##### 題目地址
<https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/>
##### 題目描述
```
<pre class="calibre18">```
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
請找出其中最小的元素。
你可以假設數組中不存在重復元素。
示例 1:
輸入: [3,4,5,1,2]
輸出: 1
示例 2:
輸入: [4,5,6,7,0,1,2]
輸出: 0
```
```
##### 二分法
###### 思路
和查找指定值得思路一樣。我們還是:
- 初始化首尾指針 l 和 r
- 如果 nums\[mid\] 大于 nums\[r\],說明 mid 在左側有序部分,由于最小的一定在右側,因此可以收縮左區間,即 l = mid + 1
- 否則收縮右側,即 r = mid(不可以 r = mid - 1)
> 這里多判斷等號沒有意義,因為題目沒有讓我們找指定值
- 當 l >= r 或者 nums\[l\] < nums\[r\] 的時候退出循環
> nums\[l\] < nums\[r\],說明區間 \[l, r\] 已經是整體有序了,因此 nums\[l\] 就是我們想要找的
###### 代碼(Python)
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMin</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span>
l, r = <span class="hljs-params">0</span>, len(nums) - <span class="hljs-params">1</span>
<span class="hljs-keyword">while</span> l < r:
<span class="hljs-title"># important</span>
<span class="hljs-keyword">if</span> nums[l] < nums[r]:
<span class="hljs-keyword">return</span> nums[l]
mid = (l + r) // <span class="hljs-params">2</span>
<span class="hljs-title"># left part</span>
<span class="hljs-keyword">if</span> nums[mid] > nums[r]:
l = mid + <span class="hljs-params">1</span>
<span class="hljs-keyword">else</span>:
<span class="hljs-title"># right part</span>
r = mid
<span class="hljs-title"># l or r is not important</span>
<span class="hljs-keyword">return</span> nums[l]
```
```
**復雜度分析**
- 時間復雜度:O(logN)O(log N)O(logN)
- 空間復雜度:O(1)O(1)O(1)
##### 另一種二分法
###### 思路
我們當然也也可以和 nums\[l\] 比較,而不是上面的 nums\[r\],我們發現:
- 旋轉點左側元素**都大于**數組第一個元素
- 旋轉點右側元素**都小于**數組第一個元素
這樣就建立了 nums\[mid\] 和 nums\[0\] 的聯系。
具體算法:
1. 找到數組的中間元素 mid。
2. 如果中間元素 > 數組第一個元素,我們需要在 mid 右邊搜索。

- 如果中間元素 <= 數組第一個元素,我們需要在 mid 左邊搜索。
上面的例子中,中間元素 6 比第一個元素 4 大,因此在中間點右側繼續搜索。
1. 當我們找到旋轉點時停止搜索,當以下條件滿足任意一個即可:
2. nums\[mid\] > nums\[mid + 1\],因此 mid+1 是最小值。
3. nums\[mid - 1\] > nums\[mid\],因此 mid 是最小值。

###### 代碼(Python)
```
<pre class="calibre18">```
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMin</span><span class="hljs-params">(self, nums)</span>:</span>
<span class="hljs-title"># If the list has just one element then return that element.</span>
<span class="hljs-keyword">if</span> len(nums) == <span class="hljs-params">1</span>:
<span class="hljs-keyword">return</span> nums[<span class="hljs-params">0</span>]
<span class="hljs-title"># left pointer</span>
left = <span class="hljs-params">0</span>
<span class="hljs-title"># right pointer</span>
right = len(nums) - <span class="hljs-params">1</span>
<span class="hljs-title"># if the last element is greater than the first element then there is no rotation.</span>
<span class="hljs-title"># e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.</span>
<span class="hljs-title"># Hence the smallest element is first element. A[0]</span>
<span class="hljs-keyword">if</span> nums[right] > nums[<span class="hljs-params">0</span>]:
<span class="hljs-keyword">return</span> nums[<span class="hljs-params">0</span>]
<span class="hljs-title"># Binary search way</span>
<span class="hljs-keyword">while</span> right >= left:
<span class="hljs-title"># Find the mid element</span>
mid = left + (right - left) / <span class="hljs-params">2</span>
<span class="hljs-title"># if the mid element is greater than its next element then mid+1 element is the smallest</span>
<span class="hljs-title"># This point would be the point of change. From higher to lower value.</span>
<span class="hljs-keyword">if</span> nums[mid] > nums[mid + <span class="hljs-params">1</span>]:
<span class="hljs-keyword">return</span> nums[mid + <span class="hljs-params">1</span>]
<span class="hljs-title"># if the mid element is lesser than its previous element then mid element is the smallest</span>
<span class="hljs-keyword">if</span> nums[mid - <span class="hljs-params">1</span>] > nums[mid]:
<span class="hljs-keyword">return</span> nums[mid]
<span class="hljs-title"># if the mid elements value is greater than the 0th element this means</span>
<span class="hljs-title"># the least value is still somewhere to the right as we are still dealing with elements greater than nums[0]</span>
<span class="hljs-keyword">if</span> nums[mid] > nums[<span class="hljs-params">0</span>]:
left = mid + <span class="hljs-params">1</span>
<span class="hljs-title"># if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left</span>
<span class="hljs-keyword">else</span>:
right = mid - <span class="hljs-params">1</span>
```
```
**復雜度分析**
- 時間復雜度:O(logN)O(log N)O(logN)
- 空間復雜度:O(1)O(1)O(1)
### 二叉樹
對于一個給定的二叉樹,其任意節點最多只有兩個子節點。 從這個定義,我們似乎可以嗅出一點二分法的味道, 但是這并不是二分。但是,二叉樹中卻和二分有很多聯系,我們來看一下。
最簡單的,如果這個二叉樹是一個二叉搜索樹(BST)。 那么實際上,在一個二叉搜索樹種進行搜索的過程就是二分法。

如上圖,我們需要在這樣一個二叉搜索樹中搜索 7。那么我們的搜索路徑則會是 8 -> 3 -> 6 -> 7,這也是一種二分法。只不過相比于普通的**有序序列查找給定值**二分, 其時間復雜度的下界更差,原因在于二叉搜索樹并不一定是二叉平衡樹。
上面講了二叉搜索樹,我們再來看一種同樣特殊的樹 - 完全二叉樹。 如果我們給一顆完全二叉樹的所有節點進行編號(二進制),依次為 01,10,11, ...。

那么實際上,最后一行的編號就是從根節點到該節點的路徑。 其中 0 表示向左, 1 表示向右。(第一位數字不用)。 我們以最后一行的 101 為例,我們需要執行一次左,然后一次右。

其實原理也不難,如果你用數組表示過完全二叉樹,那么就很容易理解。 我們可以發現, 父節點的編號都是左節點的二倍,并且都是右節點的二倍 + 1。從二進制的角度來看就是:**父節點的編號左移一位就是左節點的編號,左移一位 + 1 就是右節點的編號**。 因此反過來, 知道了子節點的最后一位,我們就能知道它是父節點的左節點還是右節點啦。
## 題目推薦
- [875. 愛吃香蕉的珂珂](https://leetcode-cn.com/problems/koko-eating-bananas/)
- [300. 最長上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/description/)
- [354. 俄羅斯套娃信封問題](https://leetcode-cn.com/problems/russian-doll-envelopes/)
- [面試題 17.08. 馬戲團人塔](https://leetcode-cn.com/problems/circus-tower-lcci/)
> 后面三個題建議一起做
## 總結
二分查找是一種非常重要且難以掌握的核心算法,大家一定要好好領會。有的題目直接二分就可以了,有的題目二分只是其中一個環節。不管是哪種,都需要我們對二分的思想和代碼模板非常熟悉才可以。
二分查找的基本題型有:
- 查找滿足條件的元素,返回對應索引
- 如果存在多個滿足條件的元素,返回最左邊滿足條件的索引。
- 如果存在多個滿足條件的元素,返回最右邊滿足條件的索引。
- 數組不是整體有序的。 比如先升序再降序,或者先降序再升序。
- 將一維數組變成二維數組。
- 局部有序查找最大(最小)元素
- 。。。
不管是哪一種類型,我們的思維框架都是類似的,都是:
- 先定義**搜索區間**(非常重要)
- 根據搜索區間定義循環結束條件
- 取中間元素和目標元素做對比(目標元素可能是需要找的元素或者是數組第一個,最后一個元素等)(非常重要)
- 根據比較的結果收縮區間,舍棄非法解(也就是二分)
> 如果是整體有序通常只需要 nums\[mid\] 和 target 比較即可。如果是局部有序,則可能需要與其周圍的特定元素進行比較。
大家可以使用這個思維框架并結合本文介紹的幾種題型進行練習,必要的情況可以使用我提供的解題模板,提供解題速度的同時,有效地降低出錯的概率。
特別需要注意的是**有無重復元素對二分算法影響很大**,我們需要小心對待。
- Introduction
- 第一章 - 算法專題
- 數據結構
- 基礎算法
- 二叉樹的遍歷
- 動態規劃
- 哈夫曼編碼和游程編碼
- 布隆過濾器
- 字符串問題
- 前綴樹專題
- 《貪婪策略》專題
- 《深度優先遍歷》專題
- 滑動窗口(思路 + 模板)
- 位運算
- 設計題
- 小島問題
- 最大公約數
- 并查集
- 前綴和
- 平衡二叉樹專題
- 第二章 - 91 天學算法
- 第一期講義-二分法
- 第一期講義-雙指針
- 第二期
- 第三章 - 精選題解
- 《日程安排》專題
- 《構造二叉樹》專題
- 字典序列刪除
- 百度的算法面試題 * 祖瑪游戲
- 西法的刷題秘籍】一次搞定前綴和
- 字節跳動的算法面試題是什么難度?
- 字節跳動的算法面試題是什么難度?(第二彈)
- 《我是你的媽媽呀》 * 第一期
- 一文帶你看懂二叉樹的序列化
- 穿上衣服我就不認識你了?來聊聊最長上升子序列
- 你的衣服我扒了 * 《最長公共子序列》
- 一文看懂《最大子序列和問題》
- 第四章 - 高頻考題(簡單)
- 面試題 17.12. BiNode
- 0001. 兩數之和
- 0020. 有效的括號
- 0021. 合并兩個有序鏈表
- 0026. 刪除排序數組中的重復項
- 0053. 最大子序和
- 0088. 合并兩個有序數組
- 0101. 對稱二叉樹
- 0104. 二叉樹的最大深度
- 0108. 將有序數組轉換為二叉搜索樹
- 0121. 買賣股票的最佳時機
- 0122. 買賣股票的最佳時機 II
- 0125. 驗證回文串
- 0136. 只出現一次的數字
- 0155. 最小棧
- 0167. 兩數之和 II * 輸入有序數組
- 0169. 多數元素
- 0172. 階乘后的零
- 0190. 顛倒二進制位
- 0191. 位1的個數
- 0198. 打家劫舍
- 0203. 移除鏈表元素
- 0206. 反轉鏈表
- 0219. 存在重復元素 II
- 0226. 翻轉二叉樹
- 0232. 用棧實現隊列
- 0263. 丑數
- 0283. 移動零
- 0342. 4的冪
- 0349. 兩個數組的交集
- 0371. 兩整數之和
- 0437. 路徑總和 III
- 0455. 分發餅干
- 0575. 分糖果
- 0874. 模擬行走機器人
- 1260. 二維網格遷移
- 1332. 刪除回文子序列
- 第五章 - 高頻考題(中等)
- 0002. 兩數相加
- 0003. 無重復字符的最長子串
- 0005. 最長回文子串
- 0011. 盛最多水的容器
- 0015. 三數之和
- 0017. 電話號碼的字母組合
- 0019. 刪除鏈表的倒數第N個節點
- 0022. 括號生成
- 0024. 兩兩交換鏈表中的節點
- 0029. 兩數相除
- 0031. 下一個排列
- 0033. 搜索旋轉排序數組
- 0039. 組合總和
- 0040. 組合總和 II
- 0046. 全排列
- 0047. 全排列 II
- 0048. 旋轉圖像
- 0049. 字母異位詞分組
- 0050. Pow(x, n)
- 0055. 跳躍游戲
- 0056. 合并區間
- 0060. 第k個排列
- 0062. 不同路徑
- 0073. 矩陣置零
- 0075. 顏色分類
- 0078. 子集
- 0079. 單詞搜索
- 0080. 刪除排序數組中的重復項 II
- 0086. 分隔鏈表
- 0090. 子集 II
- 0091. 解碼方法
- 0092. 反轉鏈表 II
- 0094. 二叉樹的中序遍歷
- 0095. 不同的二叉搜索樹 II
- 0096. 不同的二叉搜索樹
- 0098. 驗證二叉搜索樹
- 0102. 二叉樹的層序遍歷
- 0103. 二叉樹的鋸齒形層次遍歷
- 105. 從前序與中序遍歷序列構造二叉樹
- 0113. 路徑總和 II
- 0129. 求根到葉子節點數字之和
- 0130. 被圍繞的區域
- 0131. 分割回文串
- 0139. 單詞拆分
- 0144. 二叉樹的前序遍歷
- 0150. 逆波蘭表達式求值
- 0152. 乘積最大子數組
- 0199. 二叉樹的右視圖
- 0200. 島嶼數量
- 0201. 數字范圍按位與
- 0208. 實現 Trie (前綴樹)
- 0209. 長度最小的子數組
- 0211. 添加與搜索單詞 * 數據結構設計
- 0215. 數組中的第K個最大元素
- 0221. 最大正方形
- 0229. 求眾數 II
- 0230. 二叉搜索樹中第K小的元素
- 0236. 二叉樹的最近公共祖先
- 0238. 除自身以外數組的乘積
- 0240. 搜索二維矩陣 II
- 0279. 完全平方數
- 0309. 最佳買賣股票時機含冷凍期
- 0322. 零錢兌換
- 0328. 奇偶鏈表
- 0334. 遞增的三元子序列
- 0337. 打家劫舍 III
- 0343. 整數拆分
- 0365. 水壺問題
- 0378. 有序矩陣中第K小的元素
- 0380. 常數時間插入、刪除和獲取隨機元素
- 0416. 分割等和子集
- 0445. 兩數相加 II
- 0454. 四數相加 II
- 0494. 目標和
- 0516. 最長回文子序列
- 0518. 零錢兌換 II
- 0547. 朋友圈
- 0560. 和為K的子數組
- 0609. 在系統中查找重復文件
- 0611. 有效三角形的個數
- 0718. 最長重復子數組
- 0754. 到達終點數字
- 0785. 判斷二分圖
- 0820. 單詞的壓縮編碼
- 0875. 愛吃香蕉的珂珂
- 0877. 石子游戲
- 0886. 可能的二分法
- 0900. RLE 迭代器
- 0912. 排序數組
- 0935. 騎士撥號器
- 1011. 在 D 天內送達包裹的能力
- 1014. 最佳觀光組合
- 1015. 可被 K 整除的最小整數
- 1019. 鏈表中的下一個更大節點
- 1020. 飛地的數量
- 1023. 駝峰式匹配
- 1031. 兩個非重疊子數組的最大和
- 1104. 二叉樹尋路
- 1131.絕對值表達式的最大值
- 1186. 刪除一次得到子數組最大和
- 1218. 最長定差子序列
- 1227. 飛機座位分配概率
- 1261. 在受污染的二叉樹中查找元素
- 1262. 可被三整除的最大和
- 1297. 子串的最大出現次數
- 1310. 子數組異或查詢
- 1334. 閾值距離內鄰居最少的城市
- 1371.每個元音包含偶數次的最長子字符串
- 第六章 - 高頻考題(困難)
- 0004. 尋找兩個正序數組的中位數
- 0023. 合并K個升序鏈表
- 0025. K 個一組翻轉鏈表
- 0030. 串聯所有單詞的子串
- 0032. 最長有效括號
- 0042. 接雨水
- 0052. N皇后 II
- 0084. 柱狀圖中最大的矩形
- 0085. 最大矩形
- 0124. 二叉樹中的最大路徑和
- 0128. 最長連續序列
- 0145. 二叉樹的后序遍歷
- 0212. 單詞搜索 II
- 0239. 滑動窗口最大值
- 0295. 數據流的中位數
- 0301. 刪除無效的括號
- 0312. 戳氣球
- 0335. 路徑交叉
- 0460. LFU緩存
- 0472. 連接詞
- 0488. 祖瑪游戲
- 0493. 翻轉對
- 0887. 雞蛋掉落
- 0895. 最大頻率棧
- 1032. 字符流
- 1168. 水資源分配優化
- 1449. 數位成本和為目標值的最大數字
- 后序