二分查找 Python bisect 内置模块

• 第一部分 搞清 bisect 模块
• • 实例
  • 总结：
• ★35.搜索插入位置
• 2089.找出数组排序后的目标下标
• Python bisect 内置模块
• Python bisect 源码

★ 模块只针对 [升序列表]

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 的右邻居；
目标不存在，左右相同，都是大于目标的元素位置。

1. 注意是★插入位置
2. 只针对★升序。
3. target 不存在，返回右邻居的位置；存在 bisect_left 返回第一个目标位置， bisect_right
   返回最后一个目标的右邻居的位置。
4. 三者关系：bisect_left、<、i ；bisect_right、>、j
5. 条件 while i < j: 返回 i = j

★区分：插入位置与目标位置

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