在這個系列的部落格中，我們根據LeetCode官方給出的每個題目的出現頻率，整理并收錄了每個類别裡高頻出現的題目，從簡單到中等再到困難，為你提供解題技巧和最佳實踐。我們将介紹常見的算法思想，如貪心算法、動态規劃、回溯算法等，希望能幫助你提高算法水準，成為你進入人工智能行業敲門磚。
704：二分查找（難度2/頻率5）
題目連結：https://leetcode-cn.com/problems/binary-search/
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下标為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中是以傳回 -1
解題思路
本題提到數組為有序數組，同時還強調無重複元素，因為一旦有重複元素，使用二分查找法傳回的元素下标可能不是唯一的，這些都是使用二分法的前提條件，當大家看到題目描述滿足如上條件的時候，可要想一想是不是可以用二分法了。
大家寫二分法經常寫亂，主要是因為對區間的定義沒有想清楚，區間的定義就是不變量。要不信你現在可以動手寫個二分查找，一定會遇到一個問題，到底是 while(left < right) 還是 while(left <= right)，到底是right = middle呢，還是要right = middle - 1呢？在二分查找的過程中，保持不變量，就是在while尋找中每一次邊界的處理都要堅持根據區間的定義來操作，這就是循環不變量規則。
二分查找的區間是不斷疊代的，解決上述問題就一定要遵循區間定義，區間的定義一般為兩種，左閉右閉即[left, right]，或者左閉右開即[left, right)。
第一種寫法：區間左閉右閉
區間的定義決定了二分法的代碼應該如何寫，因為定義target在[left, right]區間，是以有如下兩點：
- while (left <= right) 要使用 <= ，因為left == right是有意義的，是以使用 <=
- if (nums[middle] > target) right 要指派為 middle - 1，因為目前這個nums[middle]一定不是target，那麼接下來要查找的左區間結束下标位置就是 middle - 1
例如在下列數組查找元素33，如圖所示：
遞增數組，索引為0和11
注意middle的計算
注意left的變化
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1 # 定義target在左閉右閉的區間裡，[left, right]
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1 # target在左區間，是以[left, middle - 1]
elif nums[middle] < target:
left = middle + 1 # target在右區間，是以[middle + 1, right]
else:
return middle # 數組中找到目标值，直接傳回下标
return -1 # 未找到目标值 第二種寫法：區間左閉右開
區間左閉右開，也就是[left, right) ，那麼二分法的邊界處理方式則截然不同。
有如下兩點：
- while (left < right)，這裡使用 < ,因為left == right在區間[left, right)是沒有意義的；
- if (nums[middle] > target) right 更新為 middle，因為目前nums[middle]不等于target，去左區間繼續尋找，而尋找區間是左閉右開區間，是以right更新為middle；
比如在數組：1,2,3,4,7,9,10中查找元素2，如圖所示：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) # 定義target在左閉右開的區間裡，即：[left, right)
while left < right: # 因為left == right的時候，在[left, right)是無效的空間，是以使用 <
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle # target 在左區間，在[left, middle)中
elif nums[middle] < target:
left = middle + 1 # target 在右區間，在[middle + 1, right)中
else:
return middle # 數組中找到目标值，直接傳回下标
return -1 # 未找到目标值 題目總結
二分法是非常重要的基礎算法，了解清楚區間的定義，進而更準确的處理邊界情況，其時間複雜度為（O (log2n )），再通過一個動圖讓你加深對二分法的了解。
相關題目推薦
- 35.搜尋插入位置
- 34. 在排序數組中查找元素的第一個和最後一個位置
- 69. x 的平方根
- 367.有效的完全平方數