<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <html> <head> <link rel="STYLESHEET" href="lib.css" type='text/css' /> <link rel="SHORTCUT ICON" href="../icons/pyfav.gif" /> <link rel='start' href='../index.html' title='Python Documentation Index' /> <link rel="first" href="lib.html" title='Python Library Reference' /> <link rel='contents' href='contents.html' title="Contents" /> <link rel='index' href='genindex.html' title='Index' /> <link rel='last' href='about.html' title='About this document...' /> <link rel='help' href='about.html' title='About this document...' /> <LINK rel="next" href="module-heapq.html"> <LINK rel="prev" href="module-whrandom.html"> <LINK rel="parent" href="misc.html"> <LINK rel="next" href="bisect-example.html"> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> <meta name='aesop' content='information' /> <META name="description" content="bisect -- Array bisection algorithm"> <META name="keywords" content="lib"> <META name="resource-type" content="document"> <META name="distribution" content="global"> <title>5.10 bisect -- Array bisection algorithm</title> </head> <body> <DIV CLASS="navigation"> <div id='top-navigation-panel'> <table align="center" width="100%" cellpadding="0" cellspacing="2"> <tr> <td class='online-navigation'><a rel="prev" title="5.9 whrandom " href="module-whrandom.html"><img src='../icons/previous.png' border='0' height='32' alt='Previous Page' width='32' /></A></td> <td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services" href="misc.html"><img src='../icons/up.png' border='0' height='32' alt='Up One Level' width='32' /></A></td> <td class='online-navigation'><a rel="next" title="5.10.1 Examples" href="bisect-example.html"><img src='../icons/next.png' border='0' height='32' alt='Next Page' width='32' /></A></td> <td align="center" width="100%">Python Library Reference</td> <td class='online-navigation'><a rel="contents" title="Table of Contents" href="contents.html"><img src='../icons/contents.png' border='0' height='32' alt='Contents' width='32' /></A></td> <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' border='0' height='32' alt='Module Index' width='32' /></a></td> <td class='online-navigation'><a rel="index" title="Index" href="genindex.html"><img src='../icons/index.png' border='0' height='32' alt='Index' width='32' /></A></td> </tr></table> <div class='online-navigation'> <b class="navlabel">Previous:</b> <a class="sectref" rel="prev" href="module-whrandom.html">5.9 whrandom </A> <b class="navlabel">Up:</b> <a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A> <b class="navlabel">Next:</b> <a class="sectref" rel="next" href="bisect-example.html">5.10.1 Examples</A> </div> <hr /></div> </DIV> <!--End of Navigation Panel--> <H1><A NAME="SECTION0071000000000000000000"> 5.10 <tt class="module">bisect</tt> -- Array bisection algorithm</A> </H1> <P> <A NAME="module-bisect"><!--z--></A> <P> 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 <tt class="module">bisect</tt> 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 (the boundary conditions are already right!). <P> The following functions are provided: <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1174' class="function">bisect_left</tt></b>(</nobr></td> <td><var>list, item</var><big>[</big><var>, lo</var><big>[</big><var>, hi</var><big>]</big><big>]</big>)</td></tr></table></dt> <dd> Locate the proper insertion point for <var>item</var> in <var>list</var> to maintain sorted order. The parameters <var>lo</var> and <var>hi</var> may be used to specify a subset of the list which should be considered; by default the entire list is used. If <var>item</var> is already present in <var>list</var>, 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 <code><var>list</var>.insert()</code>. This assumes that <var>list</var> is already sorted. <span class="versionnote">New in version 2.1.</span> </dl> <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1175' class="function">bisect_right</tt></b>(</nobr></td> <td><var>list, item</var><big>[</big><var>, lo</var><big>[</big><var>, hi</var><big>]</big><big>]</big>)</td></tr></table></dt> <dd> Similar to <tt class="function">bisect_left()</tt>, but returns an insertion point which comes after (to the right of) any existing entries of <var>item</var> in <var>list</var>. <span class="versionnote">New in version 2.1.</span> </dl> <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1176' class="function">bisect</tt></b>(</nobr></td> <td><var>...</var>)</td></tr></table></dt> <dd> Alias for <tt class="function">bisect_right()</tt>. </dl> <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1177' class="function">insort_left</tt></b>(</nobr></td> <td><var>list, item</var><big>[</big><var>, lo</var><big>[</big><var>, hi</var><big>]</big><big>]</big>)</td></tr></table></dt> <dd> Insert <var>item</var> in <var>list</var> in sorted order. This is equivalent to <code><var>list</var>.insert(bisect.bisect_left(<var>list</var>, <var>item</var>, <var>lo</var>, <var>hi</var>), <var>item</var>)</code>. This assumes that <var>list</var> is already sorted. <span class="versionnote">New in version 2.1.</span> </dl> <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1178' class="function">insort_right</tt></b>(</nobr></td> <td><var>list, item</var><big>[</big><var>, lo</var><big>[</big><var>, hi</var><big>]</big><big>]</big>)</td></tr></table></dt> <dd> Similar to <tt class="function">insort_left()</tt>, but inserting <var>item</var> in <var>list</var> after any existing entries of <var>item</var>. <span class="versionnote">New in version 2.1.</span> </dl> <P> <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> <td><nobr><b><tt id='l2h-1179' class="function">insort</tt></b>(</nobr></td> <td><var>...</var>)</td></tr></table></dt> <dd> Alias for <tt class="function">insort_right()</tt>. </dl> <P> <p><br /></p><hr class='online-navigation' /> <div class='online-navigation'> <!--Table of Child-Links--> <A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a> <UL CLASS="ChildLinks"> <LI><A href="bisect-example.html">5.10.1 Examples</a> </ul> <!--End of Table of Child-Links--> </div> <DIV CLASS="navigation"> <div class='online-navigation'><hr /> <table align="center" width="100%" cellpadding="0" cellspacing="2"> <tr> <td class='online-navigation'><a rel="prev" title="5.9 whrandom " rel="prev" title="5.9 whrandom " href="module-whrandom.html"><img src='../icons/previous.png' border='0' height='32' alt='Previous Page' width='32' /></A></td> <td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services" rel="parent" title="5. Miscellaneous Services" href="misc.html"><img src='../icons/up.png' border='0' height='32' alt='Up One Level' width='32' /></A></td> <td class='online-navigation'><a rel="next" title="5.10.1 Examples" rel="next" title="5.10.1 Examples" href="bisect-example.html"><img src='../icons/next.png' border='0' height='32' alt='Next Page' width='32' /></A></td> <td align="center" width="100%">Python Library Reference</td> <td class='online-navigation'><a rel="contents" title="Table of Contents" rel="contents" title="Table of Contents" href="contents.html"><img src='../icons/contents.png' border='0' height='32' alt='Contents' width='32' /></A></td> <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' border='0' height='32' alt='Module Index' width='32' /></a></td> <td class='online-navigation'><a rel="index" title="Index" rel="index" title="Index" href="genindex.html"><img src='../icons/index.png' border='0' height='32' alt='Index' width='32' /></A></td> </tr></table> <div class='online-navigation'> <b class="navlabel">Previous:</b> <a class="sectref" rel="prev" href="module-whrandom.html">5.9 whrandom </A> <b class="navlabel">Up:</b> <a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A> <b class="navlabel">Next:</b> <a class="sectref" rel="next" href="bisect-example.html">5.10.1 Examples</A> </div> </div> <hr /> <span class="release-info">Release 2.3.4, documentation updated on May 20, 2004.</span> </DIV> <!--End of Navigation Panel--> <ADDRESS> See <i><a href="about.html">About this document...</a></i> for information on suggesting changes. </ADDRESS> </BODY> </HTML>