bisect

This is a Python module for inserting and sorting ordered arrays

Let’s start by looking at the methods in bisect

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

bisect
bisect_left
bisect_right
insort
insort_left
insort_right
Copy the code

Bisect is called bisect_right

Insort is called insort_right

bisect

Bisect calls 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 the code

Do not believe you look at the source code

bisect = bisect_right   # backward compatibility
Copy the code

It can be explained in one sentence

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

— The purpose is to find where the value will be inserted and return, not inserted. Returns the position to the left of x if x exists in A

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 the code

The source code is as follows

Def bisect_left(a, x, lo=0, hi=None): def bisect_left(a, x, lo=0, hi=None): def bisect_left(a, x, lo=0, hi=None): def bisect_left(a, x, lo=0, hi=None) Raise ValueError('lo must be non-negative') # raise ValueError('lo must be non-negative') # Raise ValueError('lo must be non-negative') # Raise ValueError('lo must be non-negative') # If hi is None: hi = len(a) # Mid = (lo+hi)//2 if a[mid] < x: lo = mid+1 else: hi = mid #Copy the code

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

— The purpose is to find where the value will be inserted and return, not inserted. Returns the position to the right of x if x exists in A

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 the code

The source code is as follows

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

    If the starting position is less than 0, an error is reported
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # Default to the length of the list if there is no end position
    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 position only
    return lo
Copy the code

insort

insort

Insert element X into list A and keep sorting after sorting. If x is already in A, insert it to the right of the right x.

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 the code
  • Insort is actually calling insort_right

Do not believe you look at the source code

insort = insort_right   # backward compatibility
Copy the code

It can be explained in one sentence

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

  • Insert element X into list A and keep sorting after sorting. If x is already in A, insert it to the left of the right x.
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 the code

The source code is as follows

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

    If the starting position is less than 0, an error is reported
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # Default to the length of the list if there is no end position
    if hi is None:
        hi = len(a)
    # binary search
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    # insert
    a.insert(lo, x)
Copy the code

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

Insert element X into list A and keep sorting after sorting. If x is already in A, insert it to the right of the right x.

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 the code

The source code is as follows

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

    If the starting position is less than 0, an error is reported
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # Default to the length of the list if there is no end position
    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 the code