说说 Python 的 bisect 模块

本是古典何须时尚 2022-12-11 13:35 125阅读 0赞

bisect 模块包含两个主要函数（ bisect 和 insort），它们内部利用二分查找算法，分别用于在有序序列中查找元素与插入元素。

> bisect /baɪˈsekt/  
> to divide sth into two equal parts 对半分；二等分

## 1 bisect 函数 ##

Luciano Ramalho 举了这样一个在干草垛中找针的示例来说明如何使用 bisect.bisect 与 bisect.bisect\_left。

![a03083a6b1b698120d2c9b49bd1f2465.png][]

HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
    NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 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)
            offset = position * '  |'
            print(ROW_FMT.format(needle, position, offset))
    
    
    if __name__ == '__main__':
    
        if sys.argv[-1] == 'left':
            bisect_fn = bisect.bisect_left
        else:
            bisect_fn = bisect.bisect
    
        print('DEMO:', bisect_fn.__name__)
        print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
        demo(bisect_fn)

运行结果：

DEMO: bisect_right
    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

Python 函数的一个特点是可以把函数名作为入参，比如示例中的 bisect\_fn。这样做让函数变得更加灵活，我们可以把函数名作为程序运行参数，动态加载。

HAYSTACK 是干草垛堆，NEEDLES 是针堆。在干草垛中找针，本质上是在已排好序的数列中，找某个数。

自定义的 demo(bisect\_fn) 函数，首先算出 position，然后利用位置计算出需要几个分隔符号作为打印偏移量，最后按照定义好的格式打印出来。

str.format() 用于格式化字符串，它可以指定实参位置。类似 \{0:2d\} 的语法中的 0 表示第一个入参，:2d 表示总长度，如果不足，以空格作为占位符；d 表示十进制有符号整数。

str.format() 格式中还可以设定对齐方式。^、<、>分别表示居中、左对齐、右对齐。所以 \{0:<2d\} 表示第 1 个入参左对齐且占两位的十进制有符号整数。

`__name__` 是 python 的内置类属性，存在于一个 python 程序中，代表对应程序名称。如果是主线程，那么它的内置名称就是 `__main__`。

如果在运行程序时加上 left 参数，那么在程序自定义的函数内部就会调用 bisect\_left 函数。bisect 函数其实是 bisect\_right 函数的别名。

bisect\_left 函数与bisect 函数之间的区别是：

1.  bisect\_left 函数会返回原序列中跟被插入元素相等的元素位置，如果插入新元素，那么这个新元素会被放置在与它相等的元素**前面**。  
    2.bisect 函数会返回原序列中跟被插入元素相等的元素之后的位置，如果插入新元素，那么这个新元素会被放置在与它相等的元素**后面**。

![1e29f2b09addb0526150ad8ab0cff193.png][]

bisect\_left 函数运行结果：

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

python 官方文档还举了一个利用 bisect 函数，来输出考试成绩的示例程序：

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
        i = bisect.bisect(breakpoints, score)
        return grades[i]
    
    if __name__ == '__main__':
      results = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
        logging.info('results -> %s', results)

运行结果：

INFO - results -> ['F', 'A', 'C', 'C', 'B', 'A', 'A']

自定义的 grade() 定义了三个参数：

<table> 
 <thead> 
  <tr> 
   <th>参数名</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>score</td> 
   <td>考试分数</td> 
  </tr> 
  <tr> 
   <td>breakpoints</td> 
   <td>分数等级边界值；这里分为 5 档；90 及以上、80 ~ 89、70 ~ 79、60 ~ 69 以及 60 以下。</td> 
  </tr> 
  <tr> 
   <td>grades</td> 
   <td>评测分范围。</td> 
  </tr> 
 </tbody> 
</table>

grade() 函数首先根据传入的分数，通过 bisect() 函数找出其所在位置，然后把这一位置传入 grades 序列得到评测分。

在主线程中，通过 for in 语法迭代表示学生成绩的序列，把成绩传入 grade() 函数计算出评测分，最后通过序列一次性输出。

## 2 insort 函数 ##

因为排序是一项很耗时的工作，所以对于一个有序的序列来说，新增一个元素时，最好是仍然保持有序。 insort 函数在插入时，会确保这个序列始终有序。

SIZE=10
        my_list=[]
        for i in range(SIZE):
            new_item=random.randrange(SIZE*3)
            bisect.insort(my_list,new_item)
            print('%2d -> '% new_item,my_list)

运行结果：

18 ->  [18]
     8 ->  [8, 18]
    21 ->  [8, 18, 21]
     5 ->  [5, 8, 18, 21]
    19 ->  [5, 8, 18, 19, 21]
    13 ->  [5, 8, 13, 18, 19, 21]
    20 ->  [5, 8, 13, 18, 19, 20, 21]
     4 ->  [4, 5, 8, 13, 18, 19, 20, 21]
    15 ->  [4, 5, 8, 13, 15, 18, 19, 20, 21]
     2 ->  [2, 4, 5, 8, 13, 15, 18, 19, 20, 21]

randrange() 会返回给定入参范围内的随机数，但不包括边界值。

可以看到，每次插入时，序列始终保持有序。

`print('%2d -> '% new_item,my_list)` 采用了 %s 格式化语法，%2d 定义了 new\_item 值的格式，而 my\_list 会自动挂在格式之后。所以这里在第二个百分号之后没有加上括号，圈出需要格式化的参数。

insort 也有个兄弟叫 insort\_left，底层使用的是 bisect\_left。insort\_left 函数会把新元素放置在与它相等的元素前面。

--------------------

另外 bisect 函数与insort 函数，都有两个可选参数（lo 与 hi），利用它们可以缩小需要查找的序列范围。lo 的默认值是 0，hi 的默认值是序列的长度。

[a03083a6b1b698120d2c9b49bd1f2465.png]: /images/20221123/69f35348216048c4a637c6c4729066dc.png
[1e29f2b09addb0526150ad8ab0cff193.png]: /images/20221123/049957c7081040238965dcbc5db77356.png