Python bisect module

bisect

—— This is a python For Insert and sort ordered arrays A module of

First look at it. bisect There are some methods in this module

import bisect
[print(i) for i in dir(bisect)if i.find('__') == -1]

bisect
bisect_left
bisect_right
insort
insort_left
insort_right
 Copy code 

bisect It's called bisect_right

insort It's called Of insort_right

bisect

—— Actually bisect That's calling bisect_right

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
print(bisect.bisect(li, 3))

[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

If you don't believe it, look at the source code

bisect = bisect_right   # backward compatibility
 Copy code 

One sentence can explain

bisect_left(a, x, lo=0, hi=None)

—— The purpose is to find where the value will be inserted and return , Instead of inserting . If x It exists in a Middle returns x On the left

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
print(bisect.bisect_left(li, 3))

[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

Source code is as follows

def bisect_left(a, x, lo=0, hi=None):
    # a  Original list 
    # x  The elements inserted 
    # lo  The starting position   The default value is 0
    # hi  End position   The default value is len(a)    

    #  If the starting position is less than 0  False report 
    if lo < 0:
        raise ValueError('lo must be non-negative')
    #  without   End position   be   The default is   The length of the list 
    if hi is None:
        hi = len(a)
    #  Dichotomy 
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    #  Return to location only 
    return lo
 Copy code 

bisect_right(a, x, lo=0, hi=None)

—— The purpose is to find where the value will be inserted and return , Instead of inserting . If x It exists in a Middle returns x On the right

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
print(bisect.bisect_right(li, 3))

[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

Source code is as follows

def bisect_right(a, x, lo=0, hi=None):
    # a  Original list 
    # x  The elements inserted 
    # lo  The starting position   The default value is 0
    # hi  End position   The default value is len(a) 

    #  If the starting position is less than 0  False report 
    if lo < 0:
        raise ValueError('lo must be non-negative')
    #  without   End position   be   The default is   The length of the list 
    if hi is None:
        hi = len(a)
    #  Dichotomy 
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    #  Return to location only 
    return lo
 Copy code 

insort

insort

—— In the list a Insert elements in x, And keep sorting after sorting . If x Already in a in , Insert it into the right x To the right of .

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
bisect.insort(li, 3.0)
print(li)

[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
[1, 3, 3.0, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

• Actually insort That's calling insort_right

If you don't believe it, look at the source code

insort = insort_right   # backward compatibility
 Copy code 

One sentence can explain

insort_left(a, x, lo=0, hi=None)

• In the list a Insert elements in x, And keep sorting after sorting . If x Already in a in , Insert it into the right x Left side .

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
bisect.insort_left(li, 3.0)
print(li)

[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
[1, 3.0, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

Source code is as follows

def insort_left(a, x, lo=0, hi=None):
    # a  Original list 
    # x  The elements inserted 
    # lo  The starting position   The default value is 0
    # hi  End position   The default value is len(a)

    #  If the starting position is less than 0  False report 
    if lo < 0:
        raise ValueError('lo must be non-negative')
    #  without   End position   be   The default is   The length of the list 
    if hi is None:
        hi = len(a)
    #  Two points search 
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    #  Insert 
    a.insert(lo, x)
 Copy code 

insort_right(a, x, lo=0, hi=None)

—— In the list a Insert elements in x, And keep sorting after sorting . If x Already in a in , Insert it into the right x To the right of .

import bisect

li = [1, 23, 45, 12, 23, 42, 54, 123, 14, 52, 3]
li.sort()
print(li)
bisect.insort_right(li, 3.0)
print(li)


[1, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
[1, 3.0, 3, 12, 14, 23, 23, 42, 45, 52, 54, 123]
 Copy code 

Source code is as follows

def insort_right(a, x, lo=0, hi=None):
    # a  Original list 
    # x  The elements inserted 
    # lo  The starting position   The default value is 0
    # hi  End position   The default value is len(a)

    #  If the starting position is less than 0  False report 
    if lo < 0:
        raise ValueError('lo must be non-negative')
    #  without   End position   be   The default is   The length of the list 
    if hi is None:
        hi = len(a)
    #  Binary search  
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    #  Insert 
    a.insert(lo, x)
 Copy code