二分查找的定義如下（引自Wiki）：

在計算機科學中，二分查找算法（英語：binary search algorithm），也稱折半搜索算法（英語：half-interval search algorithm）、對數搜索算法（英語：logarithmic search algorithm），是一種在有序數組中查找某一特定元素的搜索算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

二分查找算法在最壞情況下是對數時間復雜度的，需要進行 O(logn) 次比較操作（n在此處是數組的元素數量，O是大O記號，log 是對數）。二分查找算法使用常數空間，對于任何大小的輸入數據，算法使用的空間都是一樣的。除非輸入數據數量很少，否則二分查找算法比線性搜索更快，但數組必須事先被排序。盡管一些特定的、為了快速搜索而設計的數據結構更有效（比如哈希表），二分查找算法應用面更廣。

總結一句，由于二分必須在有序數組中進行，看到題目條件有有序數組的話就應該想到二分查找。

Leetbook上有關于二分查找的內容，但還是局限在多個模板套用上，且題目與知識點對應不上。更推薦的是這篇文章，真正做到了理解核心而不是套用模板。

二分查找中使用的術語：

目標 Target —— 你要查找的值
索引 Index —— 你要查找的當前位置
左、右指示符 Left，Right —— 我們用來維持查找空間的指標
中間指示符 Mid —— 我們用來應用條件來確定我們應該向左查找還是向右查找的索引

下面我們結合題目來解析二分查找的思路：

704. 二分查找

class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while left < right:mid = (left + right) // 2if nums[mid] < target:left = mid + 1else:right = midif nums[left] == target:return leftreturn -1

首先是左右指示符的設置，left = 0 與 right = len(nums) - 1 基本上每題開頭都是把整個區間作為我們想進行二分查找的區間，當然也有例外，后面會看到。

然后就是求中間指示符 mid 的環節，mid = (left + right) // 2 ，這里更推薦 mid = left + (right - left) // 2 的寫法因為要防止 left + right 整形溢出。同時我們要注意到，// 2 相當于是向下取整的，如果是希望向上取整則寫成mid = (left + right + 1) // 2 或者 mid = left + (right - left + 1) // 2 。向下取整時 mid 就會被分到左邊，向上取整時 mid 就會被分到右邊。

緊接著就是二分的核心部分，區間的劃分了。很多模板會把區間劃分為等于 target、大于 target 和小于 target 三個區間，實際上是有點繞了。此處我們統一每次只劃分兩個區間，可能存在目標元素的區間和一定不存在目標元素的區間，那么可能存在目標元素的區間要么在左邊要么在右邊，兩種可能。

又根據 mid 是被劃分在左邊的區間還是右邊的區間，得到兩種分法。因此共有4種情況，如下圖所示：

分法一（默認） mid = (left + right) // 2
第一種情況：mid 在左邊區間，目標元素在右邊區間，則 left = mid + 1；
第二種情況：mid 在左邊區間，目標元素在左邊區間，則 right = mid；

分法二 mid = (left + right + 1) // 2
第三種情況：mid 在右邊區間，目標元素在右邊區間，則 left = mid；
第四種情況：mid 在右邊區間，目標元素在左邊區間，則 right= mid - 1。

其中第一種和第二種情況一定同時出現（分法一），第三種和第四種情況一定同時出現（分法二）。然后，我們來考慮下如果只剩下兩個元素的情形，如下圖所示：

如果是分法一，即left = mid + 1與right = mid，此時 mid 必須等于 left，即向下取整，下一步才會有 left = mid + 1 = right 或者 right = mid = left，得到 left == right 從而退出循環。

如果是分法二，即left = mid與right = mid - 1，此時 mid 必須等于 right，即向上取整，下一步才會有 right = mid - 1 = left 或者 left = mid = right，得到 left == right 從而退出循環。

他們的共同點是，最后退出循環時 left 一定等于右邊的那個元素（mid + 1）。

最后，可知退出循環后一定有 left == right，如果 left （或者 right，一樣的）滿足條件（例如 nums[left] == target），則返回 left（或者right）。

35. 搜索插入位置

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 特殊情況if nums[-1] < target:return len(nums)left = 0right = len(nums)- 1while left < right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1else:right = midreturn left

本題與704題基本一樣，區別只是不要求找到一樣的元素，而是要找到第一個大于等于 target 的元素索引。此處使用的還是分法一，向下取整 mid = left + (right - left) // 2，mid 一定在左邊的區間，if nums[mid] < target即左邊的區間小于 target，那么第一個大于等于 target 的元素一定在右邊的區間，因此到右邊的區間去尋找元素， left = mid + 1。循環結束之后，一定有 left == right，由于它們的區間 [left, right] 一定有第一個大于等于 target 的元素，所以最后區間只有一個元素，它的索引 left 即為所求。

162. 尋找峰值

class Solution:def findPeakElement(self, nums: List[int]) -> int:length = len(nums)left, right = 0, length - 1while left < right:mid = left + (right - left) // 2if nums[mid] < nums[mid + 1]:left = mid + 1else:right = midreturn left

找到大于左右相鄰元素的值，若 nums[mid] < nums[mid + 1]，則目標區間在右邊，剩下兩個元素時，mid向下取整等于left，可以取到更大值 left = mid + 1 = right。

34. 在排序數組中查找元素的第一個和最后一個位置

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:length = len(nums)# 特殊情況if (not nums) or nums[-1] < target or nums[0] > target or length == 0:return [-1, -1]# 找左邊界left1, right1 = 0, length - 1while left1 < right1:mid1 = left1 + (right1 - left1) // 2 # 向下取整if nums[mid1] < target:left1 = mid1 + 1else:right1 = mid1# 數組中不存在targetif nums[left1] != target:return [-1, -1]# 找右邊界left2, right2 = left1, length - 1 # 此處優化了，找右邊界的過程從left1到length - 1的區間中找while left2 < right2:mid2 = left2 + (right2 - left2 + 1) // 2 # 向上取整if nums[mid2] > target:right2 = mid2 - 1else:left2 = mid2return [left1, right2]

本題可以看作是704題的高階版，數組中的元素是可能重復的，然后要找 target 在數組出現的第一個位置和最后一個位置。

在找第一個位置的時候，可以借助35題的思路，什么樣的位置是第一次出現的位置呢？那就是第一個大于等于 target 的元素位置。還是用的分法一，判斷條件是 if nums[mid1] < target，如果 mid1 小于 target 即左邊的區間小于 target，所以右邊的區間大于等于 target，到右邊區間繼續找left1 = mid1 + 1。循環結束后由于題目是要求 target 出現，所以判斷 nums[left1] 與 target 是否相等，相等才繼續。

然后找最后一個位置，顯然，這相當于找第一個小于等于 target 的元素位置，用分法一，判斷條件為 if nums[mid2] > target，如果 mid2 大于 target 即左邊的區間大于 target，所以右邊的區間小于等于 target，等等，順序不對？？？左邊的區間大于 target，左邊的區間又小于右邊的區間，怎么可能右邊的區間小于等于 target 呢？因此，我們要改用分法二，向上取整，把 mid2 歸到右邊的區間，判斷條件還是 if nums[mid2] > target，如果 mid2 大于 target 即右邊的區間大于 target，所以左邊的區間小于等于 target，到左邊區間繼續找right2 = mid2 - 1。能進行到這里說明 target 肯定會出現了，所以不用判斷 nums[right2 ] 與 target 是否相等，直接返回答案。

33. 搜索旋轉排序數組

class Solution:def search(self, nums: List[int], target: int) -> int:length = len(nums)if not nums:return -1left, right = 0, length - 1while left < right:mid = left + (right- left) // 2 # 分法一，mid在左邊區間，向下取整if nums[mid] < nums[right]: # mid所在位置元素小于最右邊元素，說明右邊區間有序if nums[mid] < target <= nums[right]: # 如果target在右邊區間left = mid + 1else: # 否則在左邊區間right = midelse: # mid所在位置元素大于（不會等于）最右邊元素，說明左邊區間有序if nums[left] <= target <= nums[mid]: # 如果target在左邊區間（mid也在左邊區間，可能等于target）right = midelse: # 否則在右邊區間left = mid + 1if nums[left] == target: # 等于目標值return leftelse: # 不存在目標值return -1

這題的數組是循環有序，對于 mid 來說，要么是 mid 所在的左邊區間（分法一）有序，要么是右邊區間有序，所以首先要判斷哪個區間有序，再到有序區間進行 target 的尋找（因為 mid 與 target 的比較一定是在有序區間進行的）。

右邊區間有序，判斷條件是 if nums[mid] < target <= nums[right] ，第一個取小于號是因為 mid 在左邊區間，一定小于在右邊區間的 target，而第二個取小于等于號是因為 target 可能是最右邊的元素。

左邊區間有序，判斷條件是 if nums[left] <= target <= nums[mid]，同理，target 和 mid 都在左邊區間，都可能等于最左邊的元素。

81. 搜索旋轉排序數組 II

分法一：

class Solution:def search(self, nums: List[int], target: int) -> bool:length = len(nums)left, right = 0, length - 1while left < right:mid = left + (right - left) // 2if nums[mid] < nums[right]: # 右邊區間一定有序if nums[mid] < target <= nums[right]:left = mid + 1else:right = midelif nums[mid] > nums[right]: # 左邊區間一定有序（旋轉點在右邊區間）if nums[left] <= target <= nums[mid]:right = midelse:left = mid + 1else: # 無法判斷是否有序，例如[3, 1, 2, 3, 3, 3, 3]if nums[right] == target:return Trueelse:right -= 1return nums[left] == target

分法二：

class Solution:def search(self, nums: List[int], target: int) -> bool:length = len(nums)left, right = 0, length - 1while left < right:mid = left + (right - left + 1) // 2if nums[mid] < nums[right]: # 右邊區間一定有序if nums[mid] <= target <= nums[right]:left = midelse:right = mid - 1elif nums[mid] > nums[right]: # 左邊區間一定有序（旋轉點在右邊區間）if nums[left] <= target < nums[mid]:right = mid - 1else:left = midelse: # 無法判斷是否有序，例如[3, 1, 2, 3, 3, 3, 3]if nums[right] == target:return Trueelse:right -= 1return nums[left] == target

作為33題的進階版，這道題難在數組中的元素是可能相同的，如果出現 nums[mid] == nums[right] 的情況，無法判斷左邊區間還是右邊區間是有序的。解決方法就是對于這種情況，每次縮減 right - 1 即右邊界左移一位，直到可以判斷左右區間哪個有序為止。

題解既有分法一也有分法二，他們的核心區別是分法一把 mid 歸到左邊區間，分法二把 mid 歸到右邊區間。由此導致了向下與向上取整的不同、尋找目標區間的左右邊界更新位置不同、以及 mid 與左右區間元素的大小關系不同。

153. 尋找旋轉排序數組中的最小值

class Solution:def findMin(self, nums: List[int]) -> int:length = len(nums)left, right = 0, length - 1while left < right:mid = left + (right - left) // 2if nums[mid] < nums[right]: # 右邊區間有序，拐點一定在左邊區間right = midelse: # 右邊區間無序，拐點一定在右邊區間left = mid + 1return nums[left]

本題由于沒有 target，甚至比33題還要簡單，只需要不斷地找無序的區間（同時也是拐點所在的區間）即可，由剩余兩個元素時的情況可以知道，退出循環時必然 left 等于右邊的元素，即拐點的右邊（最小值）。

154. 尋找旋轉排序數組中的最小值 II

class Solution:def findMin(self, nums: List[int]) -> int:length = len(nums)left, right = 0, length - 1while left < right:mid = left + (right - left) // 2if nums[mid] < nums[right]: # 右邊區間有序，拐點一定在左邊區間right = midelif nums[mid] > nums[right]: # 右邊區間無序，拐點一定在右邊區間left = mid + 1else: # mid與右邊界相等，無法判斷，只能縮小范圍right -= 1return nums[left]

本題是153題的進階版，與81題類似，就是多了元素可能重復這個條件。由于存在無法判斷是否有序的情況，所以要單獨討論，出現這種情況時就縮小范圍 right -= 1，其余情況還是正常找拐點所在區間。

658. 找到 K 個最接近的元素

class Solution:def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:n = len(arr)# 最小的起點為0，最大的起點為n-k，這樣才能保證選取長度為k的連續子數組low, high = 0, n - k # 框長度為k,所以起點范圍[0, n-k]while low < high:mid = (low + high) // 2if x - arr[mid] <= arr[mid + k] - x: # x更靠近左邊的元素,我們的框應該往左邊找high = midelse: # x更靠近右邊的元素,我們的框應該往右邊找low = mid + 1return arr[low: low + k]

這題雖然代碼很基本，但是思路不容易。找到 k 個與 x 最接近的數，可以把這 k 個數看作是一個長度為 k 的框，則框的左起點的范圍是 [0, n-k]。然后二分查找這個左起點，若 x 與目前左起點 arr[mid] 的距離小于等于 x 與右起點 arr[mid + k] 的距離，if x - arr[mid] <= arr[mid + k] - x:，則框應該向左移，即左起點的取值范圍從右邊縮小， high = mid，反之從左邊縮小，最后得到最接近 x 的 k 個數（框）。

總結

以上是生活随笔為你收集整理的二分查找基础概念与经典题目（Leetcode题解-Python语言）二分索引型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。