Bisect -- insert new data into the list and keep it in order

Official website

bisect—— Website to explain
This module provides support for ordered lists , So that they can still be in order when inserting new data . For long lists , If the comparison operation of its containing elements is very expensive , This can be an improvement on the more common approach .
This module is called bisect Because of its Used the basic dichotomy （bisection） Algorithm . The source code can also be used as a great algorithm example （ The boundary judgment is also done ！）

Four ways

bisect.bisect_left(a, x, lo=0, hi=len(a))
stay a Find x Appropriate insertion points to maintain order . Parameters lo and hi It can be used to identify subsets that need to be considered ; By default, the entire list is used . If x Already in a In existence , Then the insertion point will be before the existing element （ On the left ）. If a Is a list of （list） Words , The return value can be placed in list.insert() The first parameter of .
The insertion point returned i You can put arrays a In two parts .
On the left is all(val < x for val in a[lo:i]) ,
The right side is all(val >= x for val in a[i:hi]) .

bisect.bisect_right(a, x, lo=0, hi=len(a))
Be similar to bisect_left(), The insertion point returned is a Element already exists in x The right side of the .
The insertion point returned i You can put arrays a In two parts .
On the left is all(val <= x for val in a[lo:i]),
The right side is all(val > x for val in a[i:hi])
Pay attention to and left The difference between the equal sign of

bisect.insort_left(a, x, lo=0, hi=len(a))
take x Insert into an ordered sequence a in , And keep it in order . If a Orderly words , This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x). Note that the search is O(log n) Of , The insertion is O(n) Of .

bisect.insort_right(a, x, lo=0, hi=len(a))
Be similar to insort_left(), But put x Insert into a Element already exists in x The right side of the .

Realization principle

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

There are more cow usages ！

bisect Directly realize the ranking of grades ：

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect(breakpoints, score)
    return grades[i]

[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

And sorted() Functions are different , about bisect() In terms of functions ,key perhaps reversed Parameters don't make any sense . Because this will lead to inefficient design （ Continuous call bisect Function time , Will not “ remember ” Of keys searched in the past ）.

On the contrary , It's best to search a pre calculated list of keys , To find the index of relevant records .

data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda r: r[1])
keys = [r[1] for r in data]         # precomputed list of keys
data[bisect_left(keys, 0)]

data[bisect_left(keys, 1)]

data[bisect_left(keys, 5)]

data[bisect_left(keys, 8)]

application ：

about leetcode 1385. The distance between two arrays

Here are two arrays of integers arr1 , arr2 And an integer d , Please return the... Between two arrays Distance value .

「 Distance value 」 Number of elements defined as meeting this distance requirement ： For elements arr1[i] , There are no elements arr2[j] Satisfy
|arr1[i]-arr2[j]| <= d .

Key：
hold arr2 After the sorting , For each of these arr1 The elements in , All in arr2 in Find the corresponding nearest value , If these two adjacent values meet the distance d, Then the rest of the values are satisfied .
We need to pay attention to , There are two adjacent cases , Left and right , And at the same time meet .
The code is as follows ：

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        ans = 0
        for x in arr1:
            p = bisect.bisect_left(arr2,x)
            if p ==len(arr2) or abs(x - arr2[p])>d:
                if p == 0 or abs(x - arr2[p-1])>d:
                    ans +=1
        return ans

First time to know bisect, Amazing ！