二分搜尋法
python
概念
簡單來說就是一直把東西切一半切一半去尋找，如果中間比較小就去找上半部，中間比較大就去找下半部，這可以比我們循序搜尋快多了。
範例
最簡單的例子就是跑去玩終極密碼，一開始猜50，如果比較大就猜25，比較小就猜75:
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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))
|
終極密碼
例題
題目
我們可以考慮到直接使用二分搜尋法來執行，去找到他的對應位置，但問題出在於，如果找不到對應的值怎麼辦，那麼我們可以直接使用最接近它並且比她小的位置，為甚麼呢，因為這樣一來我們就可以回傳它應該插入的位置:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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)
|