---

title: 二分搜尋法

---

二分搜尋法

python

概念

簡單來說就是一直把東西切一半切一半去尋找，如果中間比較小就去找上半部，中間比較大就去找下半部，這可以比我們循序搜尋快多了。

範例

最簡單的例子就是跑去玩終極密碼，一開始猜50，如果比較大就猜25，比較小就猜75: def search(target): low = 0 high = 100 while low <= high: mid = (low+high)//2 print(mid) ## test if mid < target: low = mid+1 elif mid > target: high = mid-1 else: return mid print('ans:',search(60)) 終極密碼

例題

題目 我們可以考慮到直接使用二分搜尋法來執行，去找到他的對應位置，但問題出在於，如果找不到對應的值怎麼辦，那麼我們可以直接使用最接近它並且比她小的位置，為甚麼呢，因為這樣一來我們就可以回傳它應該插入的位置: class Solution: def searchInsert(self, nums: List[int], target: int) -> int: def search(arr, target): low = 0 high = len(arr)-1 while low <= high: mid = (low+high)//2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid -1 return low nums.sort() return search(nums, target)