從零開始學Python (25)\u200a—\u200a二元搜尋法模組bisect：我走回從前你往未來飛，遇見對的人錯過交叉點

Day 25 二元搜尋法模組bisect：我走回從前你往未來飛，遇見對的人錯過交叉點

註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。
https://ithelp.ithome.com.tw/articles/10247301

接下來，我們來談談二元搜尋法模組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))，
沒有特別指定的話就會當作使用整個串列考慮插入的問題。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
>>> 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而言，顯然有利用排序這點，
和沒有利用到這點會有根本性的差距，因為一個一個找，
和每次折半找，誰比較省時間就顯而易見了！

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

那麼，我們就明天見囉！

工商時間：

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode