2.8.1 用bisect来搜索
import bisect import sys 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): # 使用 bisect_fn 方法排序，此处为 bisect_right， # 在 HAYSTACK中查找 needle，needle 存在时返回 needle左侧的位置， # needle不存在返回应该插入的位置，此处为不存在 position = bisect_fn(HAYSTACK, needle) #生成offset个' |' 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读懂此节代码。
首先从 main 函数读起 if sys.argv[-1] == 'left': 此函数用来获取命令行参数，此处如果命令行输入的最后一个参数为 left，则bisect_fn = bisect.bisect_left。 否则bisect_fn = bisect.bisect。bisect模块 bisect 模块，用于维护有序列表。实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。 转自：简书-yongxinz的文章ROW_FMT = ‘{0:2d} @ {1:2d} {2}{0:<2d}’ 理解 此处为 format格式化函数{0：} {1：} {2} {0：} 代表传入的3个参数。 ROW_FMT.format(needle, position, offset) 数字与参数位置一一对应 {0:2d} 第0个参数宽度为2 {1:2d} 第1个参数宽度为2 {2} 第2个参数 {0:<2d} 第0个参数，填充右边，宽度为2 d为输出整数的十进制方式参考 书中示例为 bisect ， 而我执行为 bisect_right其次，bisect 函数其实是 bisect_right 函数的别名，后者还有个姊 妹函数叫 bisect_left。它们的区别在于，bisect_left 返回的插入 位置是原序列中跟被插入元素相等的元素的位置，也就是新元素会被放 置于它相等的元素的前面，而 bisect_right 返回的则是跟它相等的元 素之后的位置。这个细微的差别可能对于整数序列来讲没什么用，但是 对于那些值相等但是形式不同的数据类型来讲，结果就不一样了
