二分搜索 - 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

時間複雜度:O(log N) - N 是 list/array的長度
空間複雜度:O(1) - 因為沒用到新的數據結構

可以嘗試解題: