- 今天比昨天厲害 - 電子報
- Posts
- 二分搜索 - Binary Search
二分搜索 - Binary Search
學習Binary Search模板
這是什麼時刻你知道的!
今天來復習一下binary search二分搜索模板,懂的人也可以快速復習一下,不懂的人,看完影片就能大致了解基本的思路!
二分搜索模板
def binary_search(numbers: List[int], target: int) -> int:
# 左小右大
left = 0
# 為什麼要減一? 因為list的位置從零開始
right = len(numbers) - 1
# 左邊沒有小於或等於右邊的話,就繼續迴圈下去找目標
while left <= right:
# 找出中間點。二分數的重點!
# 左邊加上右邊除二
mid = (left + right) // 2
# 如果中間點位置對應的值是目標,那就找到了
if numbers[mid] == target:
return mid
# 如果中間點位置對應的值小於目標,那往右邊縮小下一次的二分搜索算法範圍
# 為什麼要往右邊? 因為左小右大,要往更大的方向去找
if numbers[mid] < target:
left = mid + 1
# 不然就是往左邊縮小,往小的地方找搜索
else:
right = mid - 1
# 找不到就依造情況return空或是別的raise exception。
return None