2.8章 bisect 模块介绍

import bisect
import random

L = list(range(20))
# print(L) [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]

find_value0 = bisect.bisect(L,5)
print(find_value0)  # 6 默认是返回查到到的值的右边的索引

find_value1 = bisect.bisect_left(L,5)
print(find_value1)  # 5  和list 内置方法index结果一样，区别是算法不同，官方文档推荐：在重大的list查找值时使用bisect

find_value2 = L.index(5)
print(find_value2)  # 5  线性查找 O(logn)

import bisect
import sys

HAYSTACK = [1,20,21,23,26,29,30]
NEEDLES = [0,22,30,31]

ROW_FMT = ‘{0:2d} @ {1:2d}    {2}{0:<2d}‘   # 这是格式化输出语法，（：表示取位数， < 表示左对齐）

def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK,needle)  # <1>

        offset = position * ‘  |‘  # <2>

        print(ROW_FMT.format(needle,position,offset))  # <3>

if __name__ == ‘__main__‘:

    if sys.argv[-1] == ‘left‘:    # 在命令行执行python文件的时候可以后面加一个参数（加的参数会以列表形式被程序接收） 这里可以加left，执行的时候就掉用bisect_left这个api
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect

    print(‘DEMO:‘,bisect_fn.__name__)  # <5>
    print(‘haystack ->‘,‘ ‘.join(‘%2d‘ % n for n in HAYSTACK))
    demo(bisect_fn)

DEMO: bisect
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |31
30 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |30
29 @ 13      |  |  |  |  |  |  |  |  |  |  |  |  |29
23 @ 11      |  |  |  |  |  |  |  |  |  |  |23
22 @  9      |  |  |  |  |  |  |  |  |22
10 @  5      |  |  |  |  |10
 8 @  5      |  |  |  |  |8 
 5 @  3      |  |  |5 
 2 @  1      |2 
 1 @  1      |1 
 0 @  0    0 

def wahaha(size):
    mylist = []
    for m in range(size):
        newitem = random.randrange(size * 2)
        bisect.insort(mylist,newitem)
        print(‘%5d ->‘ % newitem,mylist)

wahaha(10)

   14 -> [14]
    0 -> [0,14]
   15 -> [0,15]
   17 -> [0,17]
   18 -> [0,18]
   15 -> [0,18]
   14 -> [0,18]
   12 -> [0,18]
    6 -> [0,18]
   13 -> [0,18]