Binary algorithm for bisect array

This module implements the sorted queue list to maintain sorting after inserting elements. For a list with a large amount of data, inserting elements and keeping them sorted is very computationally intensive. This module implements the bisect algorithm, which is mainly implemented based on the binary algorithm.

bisect.bisect_left(a, x, lo=0, hi=len(a))

Insert element x into ordered list a, keep the order unchanged, and return the inserted position. The parameters lo and hi represent the range of the judgment list, and the default is the entire range. If the inserted element x already exists in list a, it is inserted to the left of the existing element.

Example:

#Python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_left (l, 0))

print(l)

print(bisect.bisect_left(l, 5))

print(bisect.bisect_left(l, 7))

The result output is as follows:

[3, 5 , 6, 6, 8]

0

[3, 5, 6, 6, 8]

1

4

bisect.bisect_right(a, x, lo=0, hi=len(a ))

bisect.bisect(a, x, lo=0, hi=len(a))

Find the position where x can be inserted in the ordered queue a and keep the queue in order. If the inserted value is the same as the value in the queue, it is inserted to the right of the same element and the index value of this position is returned.

Example:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_right (l, 0))

print(l)

print(bisect.bisect(l, 5))

print(bisect.bisect(l, 7))

The result output is as follows:

[3, 5 , 6, 6, 8]

0

[3, 5, 6, 6, 8]

2

4

bisect.insort_left(a, x, lo=0, hi=len(a ))

Insert an element x into queue a and sort the queue. It should be equivalent to: a.insert(bisect.bisect_left(a, x, lo, hi), x).

Example:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_left(l , 0)

print(l)

bisect.insort_left(l, 5)

print(l)

bisect.insort_left(l, 7)

print(l)

The result output is as follows:

[ 3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5 , 5, 6, 6, 7, 8]

bisect.insort_right(a, x, lo=0, hi=len(a))

bisect.insort(a, x, lo=0, hi= len(a))

Insert element x into queue a. If the same element is found, insert it to the right of the same element.

Example:

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_right(l , 0)

print(l)

bisect.insort(l, 5)

print(l)

bisect.insort(l, 7)

print(l)

The result output is as follows:

[ 3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5 , 5, 6, 6, 7, 8]

Use the above function for some simple encapsulation:

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:

'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]

                         been been —((a, x),

_left(a, x)

if i ! = Len (a): re Return a [i]

raise valueerror

use to convert to student performance to ABCDF level:

#python 3.4

IMPORT BISECT

Def Grade (score, Breakpoints =[60, 70, 80, 90], grades='FDCBA'):

i = bisect.bisect(breakpoints, score)

return grades[i]

print([33, 99, 77, 70, 89, 90, 100])

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

The result output is as follows:

[33, 99, 77 , 70, 89, 90, 100]

['F', 'A', 'C', 'C', 'B', 'A', 'A']