sam-t2/devtools/v8plus/html/python/lib/module-bisect.html

<!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.png" type="image/png" />
<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-collections.html" />
<link rel="prev" href="module-whrandom.html" />
<link rel="parent" href="misc.html" />
<link rel="next" href="bisect-example.html" />
<meta name='aesop' content='information' />
<title>5.11 bisect -- Array bisection algorithm</title>
</head>
<body>
<DIV CLASS="navigation">
<div id='top-navigation-panel' xml:id='top-navigation-panel'>
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.10 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.11.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.10 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.11.1 Examples</A>
</div>
<hr /></div>
</DIV>
<!--End of Navigation Panel-->

<H1><A NAME="SECTION0071100000000000000000">
5.11 <tt class="module">bisect</tt> --
         Array bisection algorithm</A>
</H1>

<P>
<A NAME="module-bisect"></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-1330' xml:id='l2h-1330' 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><var></var><big>]</big><var></var>)</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-1331' xml:id='l2h-1331' 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><var></var><big>]</big><var></var>)</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-1332' xml:id='l2h-1332' 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-1333' xml:id='l2h-1333' 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><var></var><big>]</big><var></var>)</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-1334' xml:id='l2h-1334' 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><var></var><big>]</big><var></var>)</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-1335' xml:id='l2h-1335' 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.11.1 Examples</a>
</ul>
<!--End of Table of Child-Links-->
</div>

<DIV CLASS="navigation">
<div class='online-navigation'>
<p></p><hr />
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.10 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.11.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.10 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.11.1 Examples</A>
</div>
</div>
<hr />
<span class="release-info">Release 2.4.2, documentation updated on 28 September 2005.</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>