二分查找
基本知識
當數據量很大適宜採用二分查找方法。
採用二分法查找時，一般來說數據需是排好序的. 其實二分查找的核心是單調, 這個數組有序這是單調的一種情況, 對於局部調單也可以使用二分查找
基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，
如果arr[k]=key，則查找成功
若key < arr[k]，則在數列的前半段中查找 (arr[low,mid-1])
若key > arr[k]，則在數列的後半段中繼續查找 (arr[mid+1,high])
根據以上步驟, 我們可以得到其時間複雜度為O(log(n))
mid的確定位置, 有三種寫法
mid = (l + r) / 2, 單l+r時,可能會因為數太大了而溢出mid = l + (r - l) / 2, 不會溢出mid = 1 + ((r - l) >> 2), 2法使用右移一位, 比除2快
跳出循環的條件
這是二分查找的難點!!
一般來說, 跳出循環的條件有兩個: low < high和low <= high
按照條件有下圖的情況:
根據這些情況, 需要根據問題, 進行具體分析
一般來說, 要返回mid的話, 邊界條件為low < high, 否則為low <= high, 當然一些問題仍然需要自己根據題目的要求進行分析
算法題
有序數組中找到num
問題: 在一個有序數組中, 找某個數是否存在
這是最簡單的二分法的算法題了
from typing import List
def find_num(lst: List[int], num: int) -> bool:
low = 0
high = len(lst) - 1
while low <= high:
mid = low + (high - low) >> 1
if num > lst[mid]:
low = mid + 1
elif num < lst[mid]:
high = mid - 1
else:
return True
return False
print(find_num([1, 2, 3, 4], 0))
print(find_num([1, 2, 3, 4], 1))
有序數組中找到>=num最左的位置
問題: 在一個有序數組中, 找>=某個數的最左的位置
如: [1, 1, 2, 2, 2, 2, 2, 2, 3]中大於等於2的數字的最左位置
題解
判斷[1, 1, 2, 2, 2, 2, 2, 2, 3]
low = 0 high = 8的mid為4
由於lst[3] = 4 < 2, 所以high = mid - 1 = 3即 從[1, 1, 2, 2]中繼續判斷
low = 0 high = 3的mid為1
由於lst[1] = 1 > 2, 所以low = mid + 1 = 2, 即 從 [2, 2]中繼續判斷
low = 2 high = 3的mid為2
由於lst[2] = 2 >= 2, 所以high = mid - 1 = 1, 由於 low > high, 跳出循環
返回low, 即右邊的那個數
代碼
from typing import List
def find_left(lst: List, num: int) -> int:
low = 0
high = len(lst) - 1
while low <= high:
mid = int((low + high) / 2)
if lst[mid] >= num:
# >= num 時滿足條件
# 但不知道前面是否還滿足, 所以需要繼續判斷
high = mid - 1
else:
# 不滿足條件
# 修改左區間
low = mid + 1
return low
print(find_left([1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4], 3)) # 8
print(find_left([1, 1, 2, 2, 2, 2, 2, 2, 3], 2)) # 2
有序數組中找到<=num最右的位置
問題: 在一個有序數組中, 找<=某個數的最右的位置
同樣與上面的問題一樣, 只不過把判斷條件換了
代碼:
from typing import List
def find_right(lst: List[int], num: int) -> int:
low = 0
high = len(lst) - 1
while low <= high:
mid = int((low + high) / 2)
if lst[mid] <= num:
low = mid + 1
else:
high = mid - 1
return high
print(find_right([1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4], 3)) # 17
print(find_right([1, 1, 2, 2, 2, 2, 2, 2, 3], 2)) # 7
局部最小值問題
什麼是局部最小值?
arr[0] < arr[1]，0位置是局部最小arr[N-1] < arr[N-2]，N-1位置是局部最小arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小
問題
給定一個數組arr，已知任何兩個相鄰的數都不相等，找到隨便一個局部最小位置返回
在Leetcode上有一道類似的題目, 不過求的是局部最大值, 見: 山脈數組的峰頂索引, 其題解見: 山脈數組的峰頂索引的題解
題解
一般來說, 解題的方向有兩個:
- 數據狀況
- 問題標準
這個問題相鄰兩個數不相等, 且求的是局部最小值, 所以可以用二分查找的方式
第一步: 比較0位置和1位置的值, 判斷0位置的值是否為局部最小的值, 是則返回
第二步: 比較N-1位置和N-2位置的值, 判斷N-1位置的值是否為局部最小的值, 是則返回
假如不是0和N-1位置均不是局部最小值, 那麼 1 到 N-2 範圍內無論如何必然存在局部最小值, 如下圖表示:
假如使用二分查找的方法, 每次去中間的值mid
判斷mid是否為局部最小值, 是則返回
否則, 比mid小的一邊必然存在局部最小值, 以此類推, 如下圖:
代碼
from typing import List
def find_min(lst: List[int]) -> int:
"""
尋找局部最小值
"""
lst_len = len(lst)
if lst_len <= 1 or lst[0] < lst[1]:
return 0
if lst[lst_len - 1] < lst[lst_len - 2]:
return lst_len - 1
# 正式處理中間
mid = 0
low = 0
high = lst_len - 1
while low < high:
mid = low + (high - low) // 2
if lst[mid - 1] > lst[mid] and lst[mid] < lst[mid + 1]:
return mid
# 取比當前數小的那邊
if lst[mid - 1] < lst[mid]:
high = mid
else:
low = mid
return mid
print(find_min([1, 2, 7, 8, 9])) # 0
print(find_min([9, 8, 7, 5, 3])) # 4
print(find_min([10, 2, 7, 8, 9])) # 1
print(find_min([10, 9, 2, 8, 11])) # 2
print(find_min([10, 9, 8, 7, 11])) # 3
print(find_min([1, 2, 7, 8, 9, 10])) # 0
print(find_min([9, 8, 7, 5, 3, 2])) # 5
print(find_min([10, 2, 7, 8, 9, 11])) # 1
print(find_min([10, 9, 2, 8, 11, 12])) # 2
print(find_min([10, 9, 8, 7, 11, 13])) # 3
print(find_min([10, 9, 8, 7, 4, 13])) # 4
