Edit File: bisect.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>8.5. bisect — Array bisection algorithm — Python 2.7.5 documentation</title> <link rel="stylesheet" href="../_static/default.css" type="text/css" /> <link rel="stylesheet" href="../_static/pygments.css" type="text/css" /> <script type="text/javascript"> var DOCUMENTATION_OPTIONS = { URL_ROOT: '../', VERSION: '2.7.5', COLLAPSE_INDEX: false, FILE_SUFFIX: '.html', HAS_SOURCE: true }; </script> <script type="text/javascript" src="../_static/jquery.js"></script> <script type="text/javascript" src="../_static/underscore.js"></script> <script type="text/javascript" src="../_static/doctools.js"></script> <script type="text/javascript" src="../_static/sidebar.js"></script> <link rel="search" type="application/opensearchdescription+xml" title="Search within Python 2.7.5 documentation" href="../_static/opensearch.xml"/> <link rel="author" title="About these documents" href="../about.html" /> <link rel="copyright" title="Copyright" href="../copyright.html" /> <link rel="top" title="Python 2.7.5 documentation" href="../index.html" /> <link rel="up" title="8. Data Types" href="datatypes.html" /> <link rel="next" title="8.6. array — Efficient arrays of numeric values" href="array.html" /> <link rel="prev" title="8.4. heapq — Heap queue algorithm" href="heapq.html" /> <link rel="shortcut icon" type="image/png" href="../_static/py.png" /> <script type="text/javascript" src="../_static/copybutton.js"></script> </head> <body> <div class="related"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" accesskey="I">index</a></li> <li class="right" > <a href="../py-modindex.html" title="Python Module Index" >modules</a> |</li> <li class="right" > <a href="array.html" title="8.6. array — Efficient arrays of numeric values" accesskey="N">next</a> |</li> <li class="right" > <a href="heapq.html" title="8.4. heapq — Heap queue algorithm" accesskey="P">previous</a> |</li> <li><img src="../_static/py.png" alt="" style="vertical-align: middle; margin-top: -1px"/></li> <li><a href="http://www.python.org/">Python</a> »</li> <li> <a href="../index.html">Python 2.7.5 documentation</a> » </li> <li><a href="index.html" >The Python Standard Library</a> »</li> <li><a href="datatypes.html" accesskey="U">8. Data Types</a> »</li> </ul> </div> <div class="document"> <div class="documentwrapper"> <div class="bodywrapper"> <div class="body"> <div class="section" id="module-bisect"> <span id="bisect-array-bisection-algorithm"></span><h1>8.5. <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-mod docutils literal"><span class="pre">bisect</span></tt></a> — Array bisection algorithm<a class="headerlink" href="#module-bisect" title="Permalink to this headline">¶</a></h1> <p class="versionadded"> <span class="versionmodified">New in version 2.1.</span></p> <p><strong>Source code:</strong> <a class="reference external" href="http://hg.python.org/cpython/file/2.7/Lib/bisect.py">Lib/bisect.py</a></p> <hr class="docutils" /> <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 <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-mod docutils literal"><span class="pre">bisect</span></tt></a> 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> <p>The following functions are provided:</p> <dl class="function"> <dt id="bisect.bisect_left"> <tt class="descclassname">bisect.</tt><tt class="descname">bisect_left</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.bisect_left" title="Permalink to this definition">¶</a></dt> <dd><p>Locate the insertion point for <em>x</em> in <em>a</em> to maintain sorted order. The parameters <em>lo</em> and <em>hi</em> may be used to specify a subset of the list which should be considered; by default the entire list is used. If <em>x</em> is already present in <em>a</em>, 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 <tt class="docutils literal"><span class="pre">list.insert()</span></tt> assuming that <em>a</em> is already sorted.</p> <p>The returned insertion point <em>i</em> partitions the array <em>a</em> into two halves so that <tt class="docutils literal"><span class="pre">all(val</span> <span class="pre"><</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">val</span> <span class="pre">in</span> <span class="pre">a[lo:i])</span></tt> for the left side and <tt class="docutils literal"><span class="pre">all(val</span> <span class="pre">>=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">val</span> <span class="pre">in</span> <span class="pre">a[i:hi])</span></tt> for the right side.</p> </dd></dl> <dl class="function"> <dt id="bisect.bisect_right"> <tt class="descclassname">bisect.</tt><tt class="descname">bisect_right</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.bisect_right" title="Permalink to this definition">¶</a></dt> <dt id="bisect.bisect"> <tt class="descclassname">bisect.</tt><tt class="descname">bisect</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.bisect" title="Permalink to this definition">¶</a></dt> <dd><p>Similar to <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><tt class="xref py py-func docutils literal"><span class="pre">bisect_left()</span></tt></a>, but returns an insertion point which comes after (to the right of) any existing entries of <em>x</em> in <em>a</em>.</p> <p>The returned insertion point <em>i</em> partitions the array <em>a</em> into two halves so that <tt class="docutils literal"><span class="pre">all(val</span> <span class="pre"><=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">val</span> <span class="pre">in</span> <span class="pre">a[lo:i])</span></tt> for the left side and <tt class="docutils literal"><span class="pre">all(val</span> <span class="pre">></span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">val</span> <span class="pre">in</span> <span class="pre">a[i:hi])</span></tt> for the right side.</p> </dd></dl> <dl class="function"> <dt id="bisect.insort_left"> <tt class="descclassname">bisect.</tt><tt class="descname">insort_left</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.insort_left" title="Permalink to this definition">¶</a></dt> <dd><p>Insert <em>x</em> in <em>a</em> in sorted order. This is equivalent to <tt class="docutils literal"><span class="pre">a.insert(bisect.bisect_left(a,</span> <span class="pre">x,</span> <span class="pre">lo,</span> <span class="pre">hi),</span> <span class="pre">x)</span></tt> assuming that <em>a</em> is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.</p> </dd></dl> <dl class="function"> <dt id="bisect.insort_right"> <tt class="descclassname">bisect.</tt><tt class="descname">insort_right</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.insort_right" title="Permalink to this definition">¶</a></dt> <dt id="bisect.insort"> <tt class="descclassname">bisect.</tt><tt class="descname">insort</tt><big>(</big><em>a</em>, <em>x</em>, <em>lo=0</em>, <em>hi=len(a)</em><big>)</big><a class="headerlink" href="#bisect.insort" title="Permalink to this definition">¶</a></dt> <dd><p>Similar to <a class="reference internal" href="#bisect.insort_left" title="bisect.insort_left"><tt class="xref py py-func docutils literal"><span class="pre">insort_left()</span></tt></a>, but inserting <em>x</em> in <em>a</em> after any existing entries of <em>x</em>.</p> </dd></dl> <div class="admonition-see-also admonition seealso"> <p class="first admonition-title">See also</p> <p class="last"><a class="reference external" href="http://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> that uses bisect to build a full-featured collection class with straight-forward search methods and support for a key-function. The keys are precomputed to save unnecessary calls to the key function during searches.</p> </div> <div class="section" id="searching-sorted-lists"> <h2>8.5.1. Searching Sorted Lists<a class="headerlink" href="#searching-sorted-lists" title="Permalink to this headline">¶</a></h2> <p>The above <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-func docutils literal"><span class="pre">bisect()</span></tt></a> functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. The following five functions show how to transform them into the standard lookups for sorted lists:</p> <div class="highlight-python"><div class="highlight"><pre><span class="k">def</span> <span class="nf">index</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> <span class="s">'Locate the leftmost value exactly equal to x'</span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="ow">and</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">:</span> <span class="k">return</span> <span class="n">i</span> <span class="k">raise</span> <span class="ne">ValueError</span> <span class="k">def</span> <span class="nf">find_lt</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> <span class="s">'Find rightmost value less than x'</span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="k">if</span> <span class="n">i</span><span class="p">:</span> <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="k">raise</span> <span class="ne">ValueError</span> <span class="k">def</span> <span class="nf">find_le</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> <span class="s">'Find rightmost value less than or equal to x'</span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_right</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="k">if</span> <span class="n">i</span><span class="p">:</span> <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="k">raise</span> <span class="ne">ValueError</span> <span class="k">def</span> <span class="nf">find_gt</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> <span class="s">'Find leftmost value greater than x'</span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_right</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">):</span> <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="k">raise</span> <span class="ne">ValueError</span> <span class="k">def</span> <span class="nf">find_ge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> <span class="s">'Find leftmost item greater than or equal to x'</span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">):</span> <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="k">raise</span> <span class="ne">ValueError</span> </pre></div> </div> </div> <div class="section" id="other-examples"> <h2>8.5.2. Other Examples<a class="headerlink" href="#other-examples" title="Permalink to this headline">¶</a></h2> <p id="bisect-example">The <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-func docutils literal"><span class="pre">bisect()</span></tt></a> function can be useful for numeric table lookups. This example uses <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-func docutils literal"><span class="pre">bisect()</span></tt></a> to look up a letter grade for an exam score (say) based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is a ‘B’, and so on:</p> <div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="k">def</span> <span class="nf">grade</span><span class="p">(</span><span class="n">score</span><span class="p">,</span> <span class="n">breakpoints</span><span class="o">=</span><span class="p">[</span><span class="mi">60</span><span class="p">,</span> <span class="mi">70</span><span class="p">,</span> <span class="mi">80</span><span class="p">,</span> <span class="mi">90</span><span class="p">],</span> <span class="n">grades</span><span class="o">=</span><span class="s">'FDCBA'</span><span class="p">):</span> <span class="go"> i = bisect(breakpoints, score)</span> <span class="go"> return grades[i]</span> <span class="gp">>>> </span><span class="p">[</span><span class="n">grade</span><span class="p">(</span><span class="n">score</span><span class="p">)</span> <span class="k">for</span> <span class="n">score</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">33</span><span class="p">,</span> <span class="mi">99</span><span class="p">,</span> <span class="mi">77</span><span class="p">,</span> <span class="mi">70</span><span class="p">,</span> <span class="mi">89</span><span class="p">,</span> <span class="mi">90</span><span class="p">,</span> <span class="mi">100</span><span class="p">]]</span> <span class="go">['F', 'A', 'C', 'C', 'B', 'A', 'A']</span> </pre></div> </div> <p>Unlike the <a class="reference internal" href="functions.html#sorted" title="sorted"><tt class="xref py py-func docutils literal"><span class="pre">sorted()</span></tt></a> function, it does not make sense for the <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><tt class="xref py py-func docutils literal"><span class="pre">bisect()</span></tt></a> functions to have <em>key</em> or <em>reversed</em> arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).</p> <p>Instead, it is better to search a list of precomputed keys to find the index of the record in question:</p> <div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="n">data</span> <span class="o">=</span> <span class="p">[(</span><span class="s">'red'</span><span class="p">,</span> <span class="mi">5</span><span class="p">),</span> <span class="p">(</span><span class="s">'blue'</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="s">'yellow'</span><span class="p">,</span> <span class="mi">8</span><span class="p">),</span> <span class="p">(</span><span class="s">'black'</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span> <span class="gp">>>> </span><span class="n">data</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">r</span><span class="p">:</span> <span class="n">r</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="gp">>>> </span><span class="n">keys</span> <span class="o">=</span> <span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="k">for</span> <span class="n">r</span> <span class="ow">in</span> <span class="n">data</span><span class="p">]</span> <span class="c"># precomputed list of keys</span> <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span> <span class="go">('black', 0)</span> <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">1</span><span class="p">)]</span> <span class="go">('blue', 1)</span> <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">5</span><span class="p">)]</span> <span class="go">('red', 5)</span> <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">8</span><span class="p">)]</span> <span class="go">('yellow', 8)</span> </pre></div> </div> </div> </div> </div> </div> </div> <div class="sphinxsidebar"> <div class="sphinxsidebarwrapper"> <h3><a href="../contents.html">Table Of Contents</a></h3> <ul> <li><a class="reference internal" href="#">8.5. <tt class="docutils literal"><span class="pre">bisect</span></tt> — Array bisection algorithm</a><ul> <li><a class="reference internal" href="#searching-sorted-lists">8.5.1. Searching Sorted Lists</a></li> <li><a class="reference internal" href="#other-examples">8.5.2. Other Examples</a></li> </ul> </li> </ul> <h4>Previous topic</h4> <p class="topless"><a href="heapq.html" title="previous chapter">8.4. <tt class="docutils literal"><span class="pre">heapq</span></tt> — Heap queue algorithm</a></p> <h4>Next topic</h4> <p class="topless"><a href="array.html" title="next chapter">8.6. <tt class="docutils literal"><span class="pre">array</span></tt> — Efficient arrays of numeric values</a></p> <h3>This Page</h3> <ul class="this-page-menu"> <li><a href="../bugs.html">Report a Bug</a></li> <li><a href="../_sources/library/bisect.txt" rel="nofollow">Show Source</a></li> </ul> <div id="searchbox" style="display: none"> <h3>Quick search</h3> <form class="search" action="../search.html" method="get"> <input type="text" name="q" /> <input type="submit" value="Go" /> <input type="hidden" name="check_keywords" value="yes" /> <input type="hidden" name="area" value="default" /> </form> <p class="searchtip" style="font-size: 90%"> Enter search terms or a module, class or function name. </p> </div> <script type="text/javascript">$('#searchbox').show(0);</script> </div> </div> <div class="clearer"></div> </div> <div class="related"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" >index</a></li> <li class="right" > <a href="../py-modindex.html" title="Python Module Index" >modules</a> |</li> <li class="right" > <a href="array.html" title="8.6. array — Efficient arrays of numeric values" >next</a> |</li> <li class="right" > <a href="heapq.html" title="8.4. heapq — Heap queue algorithm" >previous</a> |</li> <li><img src="../_static/py.png" alt="" style="vertical-align: middle; margin-top: -1px"/></li> <li><a href="http://www.python.org/">Python</a> »</li> <li> <a href="../index.html">Python 2.7.5 documentation</a> » </li> <li><a href="index.html" >The Python Standard Library</a> »</li> <li><a href="datatypes.html" >8. Data Types</a> »</li> </ul> </div> <div class="footer"> © <a href="../copyright.html">Copyright</a> 1990-2020, Python Software Foundation. <br /> The Python Software Foundation is a non-profit corporation. <a href="http://www.python.org/psf/donations/">Please donate.</a> <br /> Last updated on Oct 13, 2020. <a href="../bugs.html">Found a bug</a>? <br /> Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.1.3. </div> </body> </html>