In [1]:

    

from bisect import bisect_left, bisect_right # for binary search
import random
random.seed(77) # so that you and I get same random lists


    

In [2]:

    

a = [1, 2, 3, 3, 3, 4, 5]
bisect_left(a, 3), bisect_right(a, 3)


    

    
Out[2]:





(2, 5)

In [3]:

    

a = [2, 4, 6, 8, 10]
bisect_left(a, 5), bisect_right(a, 5)


    

    
Out[3]:





(2, 2)

In [4]:

    

# make a list of pseudo-random integers in [1, 99]
ls = [ random.randint(1, 99) for _ in range(30) ]
ls # show it


    

    
Out[4]:





[80,
 33,
 24,
 82,
 12,
 48,
 56,
 61,
 15,
 63,
 50,
 85,
 3,
 95,
 18,
 81,
 51,
 83,
 19,
 32,
 9,
 78,
 53,
 21,
 19,
 9,
 20,
 56,
 44,
 70]

In [5]:

    

ls.sort() # sort the list in-place
ls # show the sorted list; note there are some repeated elements


    

    
Out[5]:





[3,
 9,
 9,
 12,
 15,
 18,
 19,
 19,
 20,
 21,
 24,
 32,
 33,
 44,
 48,
 50,
 51,
 53,
 56,
 56,
 61,
 63,
 70,
 78,
 80,
 81,
 82,
 83,
 85,
 95]

In [6]:

    

# The number 40 is not in the sorted list.  If it were, where would it go?
bisect_left(ls, 40)


    

    
Out[6]:





13

In [7]:

    

# insert it
ls.insert(13, 40)
ls # show the new list


    

    
Out[7]:





[3,
 9,
 9,
 12,
 15,
 18,
 19,
 19,
 20,
 21,
 24,
 32,
 33,
 40,
 44,
 48,
 50,
 51,
 53,
 56,
 56,
 61,
 63,
 70,
 78,
 80,
 81,
 82,
 83,
 85,
 95]

In [8]:

    

# The number 19 appears in the list multiple times.
# Say we want a range [st, en) where st is the first element
# (inclusive) and en is last element (exclusive) that contains a 19
st, en = bisect_left(ls, 19), bisect_right(ls, 19)


    

In [9]:

    

st, en


    

    
Out[9]:





(6, 8)

In [10]:

    

ls[st:en]


    

    
Out[10]:





[19, 19]

In [11]:

    

# Of course, there also exists a total ordering over strings
# (lexicographical ordering), so we can do all the same things
# with strings
strls = ['a', 'awkward', 'awl', 'awls', 'axe', 'axes', 'bee']


    

In [12]:

    

strls == sorted(strls)


    

    
Out[12]:





True

In [13]:

    

# We want to get the range of elements that equal a query string:
st, en = bisect_left(strls, 'awl'), bisect_right(strls, 'awl')
st, en


    

    
Out[13]:





(2, 3)

In [14]:

    

# Say we want to get the range of elements that have some prefix,
# e.g. 'aw' and say that 'z' is the lexicographically greatest
# character in the alphabet.
st, en = bisect_left(strls, 'aw'), bisect_left(strls, 'ax')
st, en


    

    
Out[14]:





(1, 4)

In [15]:

    

strls[st:en]


    

    
Out[15]:





['awkward', 'awl', 'awls']

In [16]:

    

# If we can do it for any sorted list of strings, we can do it for
# a sorted list of suffixes
t = 'abaaba$'
suffixes = sorted([t[i:] for i in range(len(t))])
suffixes


    

    
Out[16]:





['$', 'a$', 'aaba$', 'aba$', 'abaaba$', 'ba$', 'baaba$']

In [17]:

    

st, en = bisect_left(suffixes, 'aba'), bisect_left(suffixes, 'abb')
st, en


    

    
Out[17]:





(3, 5)