[Python] Binary Search (bisect, insort)

bisect

回傳插入x的index ( O(long(n)) )，保持a的排序 (a是個已排序 list )
若x已存在a中則index會在a中的所有x的右/左邊

• bisect.bisect(a, x[, lo=0, hi=len(a), *, key=None])
   ≡ bisect.bisect_right(a, x[, lo=0, hi=len(a), *, key=None])                                                            
• bisect.bisect_left(a, x[, lo=0, hi=len(a), *, key=None])

搜尋插入x的index ( O(long(n)) )並插入 ( O(n) )，保持a的排序 (a是個已排序 list )
若x已存在a中則index會在a中的所有x的右/左邊

• bisect.insort(a, x[, lo=0, hi=len(a), *, key=None])
   ≡ bisect.insort_right(a, x[, lo=0, hi=len(a), *, key=None])
• bisect.insort_left(a, x[, lo=0, hi=len(a), *, key=None])

Parameters:

[lo, hi]: 搜索範圍

key: 排序方法

ex:

x = [6, 5]
array = [[8, 7], [4, 2], [8, 1], [7, 7], [10, 1]]
 
def get_sum(e):
  return e[0] + e[1]
 
i = bisect(array, get_sum(x), key=getsum)

References

1. Python Docs: bisect

Last Updated on 2024/12/19 by A1go