* 模塊只針對 [升序列表]
i, j = 0, len(a) # *[0, len(a)) 半開半閉區間
''' bisect_left 左側插入位置 '''
while i < j:
mid = i + j >> 1
if a[mid] < target: i = mid + 1 # 遞增 < i 三者關系，先判斷小於
else: j = mid
return i
''' bisect_right 右側插入位置 '''
while i < j:
mid = i + j >> 1
if a[mid] > target: j = mid # 先判斷大於
else: i = mid + 1
return i
from bisect import *
a = [1, 2, 6, 6, 6, 8] # 升序
bisect_left(a, 4) # 插入位置 2, 對應元素 6
bisect(a, 4) # 同上
bisect_left(a, 6) # 同上
bisect(a, 6) # 插入位置 5, 對應元素 8
目標存在，左是最左 x；右是最右 x 的右鄰居；
目標不存在，左右相同，都是大於目標的元素位置。
*區分：插入位置與目標位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect_left(nums, target)
# 右查找在目標存在時與眾不同，沒有重復元素，右插入位置 - 1 = 左插入位置
i = bisect_right(nums, target)
return i-1 if nums[i-1] == target else i
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
i = bisect_left(nums, target)
j = bisect_right(nums, target)
return list(range(i, j))
文檔
源代碼： Lib/bisect.py
bisect，是實現 二分 (bisection) 算法 的模塊，能夠保持序列順序不變的情況下對其進行 二分查找和插入。
import bisect
dir(bisect)
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
如果 x 已經在 a 裡存在，那麼插入點會在已存在元素之前（也就是左邊）。
左半邊 all(val < x for val in a[lo : i])
右半邊 all(val >= x for val in a[i : hi])
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)
返回的插入點是 a 中已存在元素 x 的右側。
左半邊 all(val <= x for val in a[lo : i])
右半邊 all(val > x for val in a[i : hi])
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
按照已排序順序將 x 插入到 a 中。
此函數首先會運行 bisect_left() 來定位一個插入點。 然後，它會在 a 上運行 insert() 方法在正確的位置插入 x 以保持排序順序。
bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
把 x 插入到 a 中已存在元素 x 的右側。
在 a 上運行 insert() 方法在正確的位置插入 x 以保持排序順序。
To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step.
key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.
If key is None, the elements are compared directly with no intervening function call.
二分法對於搜索一定范圍的值是很高效的。 對於定位特定的值，則字典的性能更好。
注意，使用 bisect 模塊的方法之前，要求操作對象是 有序序列（升、降）。
在序列 a 中二分查找適合元素 x 插入的位置，保證 a 仍為有序序列。
lo 和 hi 為可選參數，分別定義查找范圍/返回索引的 上限和下限，缺省時默認對 整個 序列查找。
因此，返回的位置索引 又稱為 “插入點”，將其設為 i，則序列 a 可以被劃分為兩部分，切片表示左側 a[lo, i) 和右側 a[i, hi] 。
"""Bisection algorithms."""
def insort_right(a, x, lo=0, hi=None, *, key=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if key is None: lo = bisect_right(a, x, lo, hi)
else: lo = bisect_right(a, key(x), lo, hi, key=key)
a.insert(lo, x)
def bisect_right(a, x, lo=0, hi=None, *, key=None):
"""Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e <= x, and all e in a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will insert just after the rightmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if lo < 0: raise ValueError('lo must be non-negative')
if hi is None: hi = len(a)
# Note, the comparison uses ">" to match the
# __lt__() logic in list.sort() and in heapq.
if key is None:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > x: hi = mid
else: lo = mid + 1
else:
while lo < hi:
mid = (lo + hi) // 2
if key(a[mid]) > x: hi = mid
else: lo = mid + 1
return lo
def insort_left(a, x, lo=0, hi=None, *, key=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the left of the leftmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if key is None: lo = bisect_left(a, x, lo, hi)
else: lo = bisect_left(a, key(x), lo, hi, key=key)
a.insert(lo, x)
def bisect_left(a, x, lo=0, hi=None, *, key=None):
"""Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will insert just before the leftmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if lo < 0: raise ValueError('lo must be non-negative')
if hi is None: hi = len(a)
# Note, the comparison uses "<" to match the
# __lt__() logic in list.sort() and in heapq.
if key is None:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x: lo = mid + 1
else: hi = mid
else:
while lo < hi:
mid = (lo + hi) // 2
if key(a[mid]) < x: lo = mid + 1
else: hi = mid
return lo
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
# Create aliases
bisect = bisect_right
insort = insort_right
