Python中bisect的使用

在<Think Python>中第十章的练习中，涉及到了分半查找的bisect模块。为此，在网上查阅了Python中bisect模块的相关内容。有几个链接相对权威和明白：

1>　　http://docs.python.org/2/library/bisect.html

2>　　http://www.cnblogs.com/skydesign/archive/2011/09/02/2163592.html

这里，就我有疑问的地方做个记录：
第一，bisect模块中的函数都有哪些用途。根据Python网站的参考手册，这个模块的主要用途是运用Bisection Algorithm（分半算法）在已序的列表中进行查找和插入操作。练习中使用了bisect_left(a,x)函数，这个函数给出了x元素在列表a的位置（如果x在列表中已经存在，这时给出最左元素）。当然，对应的还有bisect_right()函数。模块中也提供了插入操作insort_left(a,x)和insort_right(a,x)。其中，insort_left(a,x)的操作等同于a.insert(bisect.bisect_left(a,x),x)。

第二，对于Allen给出的练习代码中，if判断句如何理解。经过思考，发现经过分半查找之后，下表i可能会等于len(word_list)，比如元素x大于列表中的所有元素的情况。鉴于此，就需要用条件控制一下。这样，代码中的两个条件就能正确描述查找成功的情况（注意，查找失败的情况下，下表i也将停在0～len(list)的某个值上）。

i = bisect_left(word_list, word)

    if i != len(word_list) and word_list[i] == word:

        return True

    else:

        return False

巴特西

Python中bisect的使用

最新文章

热门文章