第一期講義-二分法 · ttttt

# 第一期講義-二分法 # 二分查找二分查找又稱`折半搜索算法`。狹義地來講，二分查找是一種在有序數組查找某一特定元素的搜索算法。這同時也是大多數人所知道的一種說法。實際上，廣義的二分查找是將問題的規模縮小到原有的一半。類似的，三分法就是將問題規模縮小為原來的 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">``` public int binarySearch(int[] nums, int target) { // 左右都閉合的區間 [l, r] int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; if (nums[mid] < target) // 搜索區間變為 [mid+1, right] left = mid + 1; if (nums[mid] > target) // 搜索區間變為 [left, mid - 1] right = mid - 1; } return -1; } ``` ``` ##### Python ``` <pre class="calibre18">``` def binarySearch(nums, target): # 左右都閉合的區間 [l, r] l, r = 0, len(nums) - 1 while l <= r: mid = (left + right) >> 1 if nums[mid] == target: return mid # 搜索區間變為 [mid+1, right] if nums[mid] < target: l = mid + 1 # 搜索區間變為 [left, mid - 1] if nums[mid] > target: r = mid - 1 return -1 ``` ``` ##### JavaScript ``` <pre class="calibre18">``` function binarySearch(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] == target) return mid; if (nums[mid] < target) // 搜索區間變為 [mid+1, right] left = mid + 1; if (nums[mid] > target) // 搜索區間變為 [left, mid - 1] right = mid - 1; } return -1; } ``` ``` ##### 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">``` public int binarySearchLeft(int[] nums, int target) { // 搜索區間為 [left, right] int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索區間變為 [mid+1, right] left = mid + 1; } if (nums[mid] > target) { // 搜索區間變為 [left, mid-1] right = mid - 1; } if (nums[mid] == target) { // 收縮右邊界 right = mid - 1; } } // 檢查是否越界 if (left >= nums.length || nums[left] != target) return -1; return left; } ``` ``` ##### Python ``` <pre class="calibre18">``` def binarySearchLeft(nums, target): # 左右都閉合的區間 [l, r] l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) >> 1 if nums[mid] == target: # 收縮右邊界 r = mid - 1; # 搜索區間變為 [mid+1, right] if nums[mid] < target: l = mid + 1 # 搜索區間變為 [left, mid - 1] if nums[mid] > target: r = mid - 1 if l >= len(nums) or nums[l] != target: return -1 return l ``` ``` ##### JavaScript ``` <pre class="calibre18">``` function binarySearchLeft(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] == target) // 收縮右邊界 right = mid - 1; if (nums[mid] < target) // 搜索區間變為 [mid+1, right] left = mid + 1; if (nums[mid] > target) // 搜索區間變為 [left, mid - 1] right = mid - 1; } // 檢查是否越界 if (left >= nums.length || nums[left] != target) return -1; return 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">``` public int binarySearchRight(int[] nums, int target) { // 搜索區間為 [left, right] int left = 0 int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索區間變為 [mid+1, right] left = mid + 1; } if (nums[mid] > target) { // 搜索區間變為 [left, mid-1] right = mid - 1; } if (nums[mid] == target) { // 收縮左邊界 left = mid + 1; } } // 檢查是否越界 if (right < 0 || nums[right] != target) return -1; return right; } ``` ``` ##### Python ``` <pre class="calibre18">``` def binarySearchRight(nums, target): # 左右都閉合的區間 [l, r] l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) >> 1 if nums[mid] == target: # 收縮左邊界 l = mid + 1; # 搜索區間變為 [mid+1, right] if nums[mid] < target: l = mid + 1 # 搜索區間變為 [left, mid - 1] if nums[mid] > target: r = mid - 1 if r < 0 or nums[r] != target: return -1 return r ``` ``` ##### JavaScript ``` <pre class="calibre18">``` function binarySearchRight(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor(left + (right - left) / 2); if (nums[mid] == target) // 收縮左邊界 left = mid + 1; if (nums[mid] < target) // 搜索區間變為 [mid+1, right] left = mid + 1; if (nums[mid] > target) // 搜索區間變為 [left, mid - 1] right = mid - 1; } // 檢查是否越界 if (right < 0 || nums[right] != target) return -1; return 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)為例講解一下： ![](https://img.kancloud.cn/3f/e5/3fe5c149cf84da759486f267b443c631_663x396.jpg) ![](https://img.kancloud.cn/30/5a/305aabbb82dbca36deb7e5ecd726f0c4_609x650.jpg) 接下來，我們考慮重復元素的問題。就會發生 nums\[mid\] == nums\[start\] 了，比如 30333 。這個時候，可以選擇 l 右移一位。有的同學會擔心”會不會錯失目標元素？“。其實這個擔心是多余的，前面我們已經介紹了”搜索區間“。由于搜索區間同時包含 l 和 mid ，因此去除一個 l ，我們還有 mid。假如 3 是我們要找的元素，這樣進行下去絕對不會錯過，而是收縮”搜索區間“到一個元素 3 ，我們就可以心安理得地返回 3 了。 ##### 代碼（Python） ``` <pre class="calibre18">``` class Solution: def search(self, nums, target): l, r = 0, len(nums)-1 while l <= r: mid = l + (r-l)//2 if nums[mid] == target: return True while l < mid and nums[l] == nums[mid]: # tricky part l += 1 # the first half is ordered if nums[l] <= nums[mid]: # target is in the first half if nums[l] <= target < nums[mid]: r = mid - 1 else: l = mid + 1 # the second half is ordered else: # target is in the second half if nums[mid] < target <= nums[r]: l = mid + 1 else: r = mid - 1 return False ``` ``` **復雜度分析** - 時間復雜度：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">``` class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m = len(matrix) if m == 0: return False n = len(matrix[0]) x = m - 1 y = 0 while x >= 0 and y < n: if matrix[x][y] > target: x -= 1 elif matrix[x][y] < target: y += 1 else: return True return False ``` ``` **復雜度分析** - 時間復雜度：最壞的情況是只有一行或者只有一列，此時時間復雜度為 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">``` class Solution: def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: # important if nums[l] < nums[r]: return nums[l] mid = (l + r) // 2 # left part if nums[mid] > nums[r]: l = mid + 1 else: # right part r = mid # l or r is not important return 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 右邊搜索。 ![](https://img.kancloud.cn/5f/cd/5fcd72e03e3802e74b87435a36b2177c_938x440.jpg) - 如果中間元素 <= 數組第一個元素，我們需要在 mid 左邊搜索。上面的例子中，中間元素 6 比第一個元素 4 大，因此在中間點右側繼續搜索。 1. 當我們找到旋轉點時停止搜索，當以下條件滿足任意一個即可： 2. nums\[mid\] > nums\[mid + 1\]，因此 mid+1 是最小值。 3. nums\[mid - 1\] > nums\[mid\]，因此 mid 是最小值。 ![](https://img.kancloud.cn/84/38/84388bcaba3a80b181827d61654445a8_818x378.jpg) ###### 代碼（Python） ``` <pre class="calibre18">``` class Solution: def findMin(self, nums): # If the list has just one element then return that element. if len(nums) == 1: return nums[0] # left pointer left = 0 # right pointer right = len(nums) - 1 # if the last element is greater than the first element then there is no rotation. # e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array. # Hence the smallest element is first element. A[0] if nums[right] > nums[0]: return nums[0] # Binary search way while right >= left: # Find the mid element mid = left + (right - left) / 2 # if the mid element is greater than its next element then mid+1 element is the smallest # This point would be the point of change. From higher to lower value. if nums[mid] > nums[mid + 1]: return nums[mid + 1] # if the mid element is lesser than its previous element then mid element is the smallest if nums[mid - 1] > nums[mid]: return nums[mid] # if the mid elements value is greater than the 0th element this means # the least value is still somewhere to the right as we are still dealing with elements greater than nums[0] if nums[mid] > nums[0]: left = mid + 1 # if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left else: right = mid - 1 ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(log N)O(logN) - 空間復雜度：O(1)O(1)O(1) ### 二叉樹對于一個給定的二叉樹，其任意節點最多只有兩個子節點。從這個定義，我們似乎可以嗅出一點二分法的味道，但是這并不是二分。但是，二叉樹中卻和二分有很多聯系，我們來看一下。最簡單的，如果這個二叉樹是一個二叉搜索樹（BST）。那么實際上，在一個二叉搜索樹種進行搜索的過程就是二分法。 ![](https://img.kancloud.cn/94/42/94421713589c8c40fa60f3d8bc35bd81_1280x1067.jpg) 如上圖，我們需要在這樣一個二叉搜索樹中搜索 7。那么我們的搜索路徑則會是 8 -> 3 -> 6 -> 7，這也是一種二分法。只不過相比于普通的**有序序列查找給定值**二分，其時間復雜度的下界更差，原因在于二叉搜索樹并不一定是二叉平衡樹。上面講了二叉搜索樹，我們再來看一種同樣特殊的樹 - 完全二叉樹。如果我們給一顆完全二叉樹的所有節點進行編號（二進制），依次為 01,10,11, ...。 ![](https://img.kancloud.cn/1a/c4/1ac49398fb368b63d5e3a00c17ed023a_581x305.jpg) 那么實際上，最后一行的編號就是從根節點到該節點的路徑。其中 0 表示向左， 1 表示向右。(第一位數字不用)。我們以最后一行的 101 為例，我們需要執行一次左，然后一次右。 ![](https://img.kancloud.cn/2b/80/2b80a0e5a35f45bf59d831d61da6538c_537x289.jpg) 其實原理也不難，如果你用數組表示過完全二叉樹，那么就很容易理解。我們可以發現，父節點的編號都是左節點的二倍，并且都是右節點的二倍 + 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 比較即可。如果是局部有序，則可能需要與其周圍的特定元素進行比較。大家可以使用這個思維框架并結合本文介紹的幾種題型進行練習，必要的情況可以使用我提供的解題模板，提供解題速度的同時，有效地降低出錯的概率。特別需要注意的是**有無重復元素對二分算法影響很大**，我們需要小心對待。