iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 25
0
Software Development

從零開始學Python系列 第 25

[Day 25] 從零開始學Python - 二元搜尋法模組bisect:我走回從前你往未來飛,遇見對的人錯過交叉點

註:本文同步刊載在Medium,若習慣Medium的話亦可去那邊看呦!

接下來,我們來談談二元搜尋法模組bisect。
在談bisect模組之前,我們先來談談二元搜尋法(binary search)。

二元搜尋法的原則是,
當有一串排列好的陣列/串列時,
我們可以透過每次去掉一半來迅速找到目標。
為什麼可以做到這點呢?
假定我們有一個串列lt,其長度為n,
由於是已經排列好的(由小排到大),
我們想要找到一個值target在lt中是否存在,
存在時所在的位置及不存在時應該插入的位置;
所以當我們取l=0, r=n-1的中間位置mid=(l+r)//2時,會有幾個可能:
lt[mid] > target => 代表target在mid左邊的位置,所以要搜尋的範圍就會變成0~mid-1
lt[mid] == target => 代表target在mid位置上,可以直接回傳結果
lt[mid] < target => 代表target在mid右邊的位置,所以要搜尋的範圍就會變成mid+1~r
因此,在尚未找到目標的狀況下,每次所需搜尋的範圍都會折半,
這也就是為什麼會被稱為二元或二分搜尋法的原因。

二元搜尋法的進一步實作是蠻基本的題目,
如果要嘗試不使用模組來處理的話,
可以參照[Day 7] 從LeetCode學演算法 - 0035. Search Insert Position (Easy)

在其他狀況下,如果題目重點不是考二元搜尋法,
或者在日常使用的話,則可以考慮使用bisect模組。

在使用bisect模組對某個list進行處理前,
需留意bisect已經預設這個list是排序過的狀態了
類似前一篇提到的heapq,
如果必要的話,請先對list進行一般排序的動作。
bisect的常見用法如下:(import bisect)
bisect_left/bisect_right/bisect:
取得應該插入的位置,當中left/right則代表如果碰到相同的值,
會當成要插入在所有相同的值的左邊或右邊(不給定則預設為右邊)
insort_left/insort_right/insort:
取得對應的bisect回傳index後,使用這個index來進行插入的動作。
上述所有函式的參數都是(串列名a, 要插入的值x, lo=0, hi=len(a)),
沒有特別指定的話就會當作使用整個串列考慮插入的問題。

>>> import bisect
>>> lt = [1,3,3,3,5,8,9]
>>> bisect.bisect_left(lt, 3) # 同值的最左邊
1
>>> bisect.bisect_right(lt, 3) # 同值的最右邊
4
>>> bisect.bisect(lt, 3) # 預設相當於right
4
>>> bisect.insort(lt, 3) # 實際插入
>>> lt
[1, 3, 3, 3, 3, 5, 8, 9]

順帶一提,使用bisect查找的速度,
扣除掉重覆值找到最左邊/最右邊外,
其時間複雜度為O(logN)。(log這邊是以2為底的)

讀者可能會問:
「什麼是複雜度呢?」
簡單來說,複雜度就是用來評估程式作一件事情,
其所需的時間/空間和輸入的資料大小(通常會用N表示)之間,
大致的量級關係。
以list來說,我們使用index()函式取得某個值的所在位置的話,
其時間會是線性的(linear),
也就是和list的長度成正比,我們會寫作O(N)。
對比起bisect而言,顯然有利用排序這點,
和沒有利用到這點會有根本性的差距,因為一個一個找,
和每次折半找,誰比較省時間就顯而易見了!

建議讀者有時間的話,
可以再進一步去查找一下關於基礎的複雜度分析,
因為有關程式複雜度分析,對於不論是實務上判斷不同方法之間的優劣,
或是面試的時候,回答考官你的解法的時候,
通常也都要回答關於時間複雜度及空間複雜度的問題,
所以有空的話可以先為自己打個底。

那麼,我們就明天見囉!


上一篇
[Day 24] 從零開始學Python - 資料結構模組heapq:除了前幾名以外,在座的各位都是垃圾
下一篇
[Day 26] 從零開始學Python - 科學運算NumPy:人間用多少滄桑,換多少人的瘋狂
系列文
從零開始學Python30

尚未有邦友留言

立即登入留言