註：本文同步刊載在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而言，顯然有利用排序這點，
和沒有利用到這點會有根本性的差距，因為一個一個找，
和每次折半找，誰比較省時間就顯而易見了！

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

那麼，我們就明天見囉！