GNU Info

(python2.1-lib.info)bisect

---

Next: array Prev: whrandom Up: Miscellaneous Services

---

Enter node , (file) or (file)node

Array bisection algorithm
=========================

Array bisection algorithms for binary searching.

This manual section was written by Fred L. Drake, Jr. <fdrake@acm.org>.
This module provides support for maintaining a list in sorted order
without having to sort the list after each insertion.  For long lists
of items with expensive comparison operations, this can be an
improvement over the more common approach.  The module is called
`bisect' because it uses a basic bisection algorithm to do its work.
The source code may be most useful as a working example of the
algorithm (i.e., the boundary conditions are already right!).

The following functions are provided:

`bisect_left(list, item[, lo[, hi]])'
     Locate the proper insertion point for ITEM in LIST to maintain
     sorted order.  The parameters LO and HI may be used to specify a
     subset of the list which should be considered; by default the
     entire list is used.  If ITEM is already present in LIST, the
     insertion point will be before (to the left of) any existing
     entries.  The return value is suitable for use as the first
     parameter to `LIST.insert()'.  This assumes that LIST is already
     sorted.  _Added in Python version 2.1_

`bisect_right(list, item[, lo[, hi]])'
     Similar to `bisect_left()', but returns an insertion point which
     comes after (to the right of) any existing entries of ITEM in LIST.
     _Added in Python version 2.1_

`bisect(...)'
     Alias for `bisect_right()'.

`insort_left(list, item[, lo[, hi]])'
     Insert ITEM in LIST in sorted order.  This is equivalent to
     `LIST.insert(bisect.bisect_left(LIST, ITEM, LO, HI), ITEM)'.  This
     assumes that LIST is already sorted.  _Added in Python version 2.1_

`insort_right(list, item[, lo[, hi]])'
     Similar to `insort_left()', but inserting ITEM in LIST after any
     existing entries of ITEM.  _Added in Python version 2.1_

`insort(...)'
     Alias for `insort_right()'.

bisect-example