HEX
Server: Apache
System: Linux pdx1-shared-a1-38 6.6.104-grsec-jammy+ #3 SMP Tue Sep 16 00:28:11 UTC 2025 x86_64
User: mmickelson (3396398)
PHP: 8.1.31
Disabled: NONE
$ pwd: /usr/share/doc/python3-doc/html/library/
Upload Files
File: //usr/share/doc/python3-doc/html/library/bisect.html
<!DOCTYPE html>

<html>
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>bisect — Array bisection algorithm &#8212; Python 3.10.12 documentation</title><meta name="viewport" content="width=device-width, initial-scale=1.0">
    
    <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../_static/pydoctheme.css?2022.1" />
    
    <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
    <script src="../_static/jquery.js"></script>
    <script src="../_static/underscore.js"></script>
    <script src="../_static/doctools.js"></script>
    
    <script src="../_static/sidebar.js"></script>
    
    <link rel="search" type="application/opensearchdescription+xml"
          title="Search within Python 3.10.12 documentation"
          href="../_static/opensearch.xml"/>
    <link rel="author" title="About these documents" href="../about.html" />
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="copyright" title="Copyright" href="../copyright.html" />
    <link rel="next" title="array — Efficient arrays of numeric values" href="array.html" />
    <link rel="prev" title="heapq — Heap queue algorithm" href="heapq.html" />
    <link rel="canonical" href="file:///usr/share/doc/python3.10/html/library/bisect.html" />
    
      
    

    
    <style>
      @media only screen {
        table.full-width-table {
            width: 100%;
        }
      }
    </style>
<link rel="shortcut icon" type="image/png" href="../_static/py.svg" />
            <script type="text/javascript" src="../_static/copybutton.js"></script>
            <script type="text/javascript" src="../_static/menu.js"></script> 

  </head>
<body>
<div class="mobile-nav">
    <input type="checkbox" id="menuToggler" class="toggler__input" aria-controls="navigation"
           aria-pressed="false" aria-expanded="false" role="button" aria-label="Menu" />
    <label for="menuToggler" class="toggler__label">
        <span></span>
    </label>
    <nav class="nav-content" role="navigation">
         <a href="https://www.python.org/" class="nav-logo">
             <img src="../_static/py.svg" alt="Logo"/>
         </a>
        <div class="version_switcher_placeholder"></div>
        <form role="search" class="search" action="../search.html" method="get">
            <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" viewBox="0 0 24 24" class="search-icon">
                <path fill-rule="nonzero"
                        d="M15.5 14h-.79l-.28-.27a6.5 6.5 0 001.48-5.34c-.47-2.78-2.79-5-5.59-5.34a6.505 6.505 0 00-7.27 7.27c.34 2.8 2.56 5.12 5.34 5.59a6.5 6.5 0 005.34-1.48l.27.28v.79l4.25 4.25c.41.41 1.08.41 1.49 0 .41-.41.41-1.08 0-1.49L15.5 14zm-6 0C7.01 14 5 11.99 5 9.5S7.01 5 9.5 5 14 7.01 14 9.5 11.99 14 9.5 14z" fill="#444"></path>
            </svg>
            <input type="text" name="q" aria-label="Quick search"/>
            <input type="submit" value="Go"/>
        </form>
    </nav>
    <div class="menu-wrapper">
        <nav class="menu" role="navigation" aria-label="main navigation">
            <div class="language_switcher_placeholder"></div>
  <h3><a href="../contents.html">Table of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#"><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a><ul>
<li><a class="reference internal" href="#performance-notes">Performance Notes</a></li>
<li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li>
<li><a class="reference internal" href="#examples">Examples</a></li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="heapq.html"
                        title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="array.html"
                        title="next chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">array</span></code> — Efficient arrays of numeric values</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../bugs.html">Report a Bug</a></li>
      <li>
        <a href="https://github.com/python/cpython/blob/3.10/Doc/library/bisect.rst"
            rel="nofollow">Show Source
        </a>
      </li>
    </ul>
  </div>
        </nav>
    </div>
</div>

  
    <div class="related" role="navigation" aria-label="related navigation">
      <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="array — Efficient arrays of numeric values"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="heapq.html" title="heapq — Heap queue algorithm"
             accesskey="P">previous</a> |</li>

          <li><img src="../_static/py.svg" alt="python logo" style="vertical-align: middle; margin-top: -1px"/></li>
          <li><a href="https://www.python.org/">Python</a> &#187;</li>
          <li class="switchers">
            <div class="language_switcher_placeholder"></div>
            <div class="version_switcher_placeholder"></div>
          </li>
          <li>
              
          </li>
    <li id="cpython-language-and-version">
      <a href="../index.html">3.10.12 Documentation</a> &#187;
    </li>

          <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">Data Types</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href=""><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a></li>
                <li class="right">
                    

    <div class="inline-search" role="search">
        <form class="inline-search" action="../search.html" method="get">
          <input placeholder="Quick search" aria-label="Quick search" 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>
    </div>
                     |
                </li>
            
      </ul>
    </div>    

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="module-bisect">
<span id="bisect-array-bisection-algorithm"></span><h1><a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code></a> — Array bisection algorithm<a class="headerlink" href="#module-bisect" title="Permalink to this headline">¶</a></h1>
<p><strong>Source code:</strong> <a class="reference external" href="https://github.com/python/cpython/tree/3.10/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."><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code></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="py function">
<dt class="sig sig-object py" id="bisect.bisect_left">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect_left</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><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 <code class="docutils literal notranslate"><span class="pre">list.insert()</span></code> 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 <code class="docutils literal notranslate"><span class="pre">all(val</span> <span class="pre">&lt;</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</span> <span class="pre">:</span> <span class="pre">i])</span></code> for the left side and
<code class="docutils literal notranslate"><span class="pre">all(val</span> <span class="pre">&gt;=</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</span> <span class="pre">:</span> <span class="pre">hi])</span></code> for the right side.</p>
<p><em>key</em> specifies a <a class="reference internal" href="../glossary.html#term-key-function"><span class="xref std std-term">key function</span></a> of one argument that is used to
extract a comparison key from each element in the array.  To support
searching complex records, the key function is not applied to the <em>x</em> value.</p>
<p>If <em>key</em> is <code class="docutils literal notranslate"><span class="pre">None</span></code>, the elements are compared directly with no
intervening function call.</p>
<div class="versionchanged">
<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>
</div>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="bisect.bisect_right">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect_right</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.bisect_right" title="Permalink to this definition">¶</a></dt>
<dt class="sig sig-object py" id="bisect.bisect">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><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"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_left()</span></code></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 <code class="docutils literal notranslate"><span class="pre">all(val</span> <span class="pre">&lt;=</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</span> <span class="pre">:</span> <span class="pre">i])</span></code> for the left side and
<code class="docutils literal notranslate"><span class="pre">all(val</span> <span class="pre">&gt;</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</span> <span class="pre">:</span> <span class="pre">hi])</span></code> for the right side.</p>
<p><em>key</em> specifies a <a class="reference internal" href="../glossary.html#term-key-function"><span class="xref std std-term">key function</span></a> of one argument that is used to
extract a comparison key from each element in the array.  To support
searching complex records, the key function is not applied to the <em>x</em> value.</p>
<p>If <em>key</em> is <code class="docutils literal notranslate"><span class="pre">None</span></code>, the elements are compared directly with no
intervening function call.</p>
<div class="versionchanged">
<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>
</div>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="bisect.insort_left">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort_left</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><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.</p>
<p>This function first runs <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_left()</span></code></a> to locate an insertion point.
Next, it runs the <code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code> method on <em>a</em> to insert <em>x</em> at the
appropriate position to maintain sort order.</p>
<p>To support inserting records in a table, the <em>key</em> function (if any) is
applied to <em>x</em> for the search step but not for the insertion step.</p>
<p>Keep in mind that the <code class="docutils literal notranslate"><span class="pre">O(log</span> <span class="pre">n)</span></code> search is dominated by the slow O(n)
insertion step.</p>
<div class="versionchanged">
<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>
</div>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="bisect.insort_right">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort_right</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.insort_right" title="Permalink to this definition">¶</a></dt>
<dt class="sig sig-object py" id="bisect.insort">
<span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="o"><span class="pre">*</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><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"><code class="xref py py-func docutils literal notranslate"><span class="pre">insort_left()</span></code></a>, but inserting <em>x</em> in <em>a</em> after any existing
entries of <em>x</em>.</p>
<p>This function first runs <a class="reference internal" href="#bisect.bisect_right" title="bisect.bisect_right"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_right()</span></code></a> to locate an insertion point.
Next, it runs the <code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code> method on <em>a</em> to insert <em>x</em> at the
appropriate position to maintain sort order.</p>
<p>To support inserting records in a table, the <em>key</em> function (if any) is
applied to <em>x</em> for the search step but not for the insertion step.</p>
<p>Keep in mind that the <code class="docutils literal notranslate"><span class="pre">O(log</span> <span class="pre">n)</span></code> search is dominated by the slow O(n)
insertion step.</p>
<div class="versionchanged">
<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>
</div>
</dd></dl>

<section id="performance-notes">
<h2>Performance Notes<a class="headerlink" href="#performance-notes" title="Permalink to this headline">¶</a></h2>
<p>When writing time sensitive code using <em>bisect()</em> and <em>insort()</em>, keep these
thoughts in mind:</p>
<ul class="simple">
<li><p>Bisection is effective for searching ranges of values.
For locating specific values, dictionaries are more performant.</p></li>
<li><p>The <em>insort()</em> functions are <code class="docutils literal notranslate"><span class="pre">O(n)</span></code> because the logarithmic search step
is dominated by the linear time insertion step.</p></li>
<li><p>The search functions are stateless and discard key function results after
they are used.  Consequently, if the search functions are used in a loop,
the key function may be called again and again on the same array elements.
If the key function isn’t fast, consider wrapping it with
<a class="reference internal" href="functools.html#functools.cache" title="functools.cache"><code class="xref py py-func docutils literal notranslate"><span class="pre">functools.cache()</span></code></a> to avoid duplicate computations.  Alternatively,
consider searching an array of precomputed keys to locate the insertion
point (as shown in the examples section below).</p></li>
</ul>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<ul class="simple">
<li><p><a class="reference external" href="https://grantjenks.com/docs/sortedcollections/">Sorted Collections</a> is a high performance
module that uses <em>bisect</em> to managed sorted collections of data.</p></li>
<li><p>The <a class="reference external" href="https://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> 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></li>
</ul>
</div>
</section>
<section id="searching-sorted-lists">
<h2>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."><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></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-python3 notranslate"><div class="highlight"><pre><span></span><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="s1">&#39;Locate the leftmost value exactly equal to x&#39;</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="s1">&#39;Find rightmost value less than x&#39;</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="s1">&#39;Find rightmost value less than or equal to x&#39;</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="s1">&#39;Find leftmost value greater than x&#39;</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="s1">&#39;Find leftmost item greater than or equal to x&#39;</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>
</section>
<section id="examples">
<h2>Examples<a class="headerlink" href="#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."><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></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."><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></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-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </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="s1">&#39;FDCBA&#39;</span><span class="p">):</span>
<span class="gp">... </span>    <span class="n">i</span> <span class="o">=</span> <span class="n">bisect</span><span class="p">(</span><span class="n">breakpoints</span><span class="p">,</span> <span class="n">score</span><span class="p">)</span>
<span class="gp">... </span>    <span class="k">return</span> <span class="n">grades</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<span class="gp">...</span>
<span class="gp">&gt;&gt;&gt; </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">[&#39;F&#39;, &#39;A&#39;, &#39;C&#39;, &#39;C&#39;, &#39;B&#39;, &#39;A&#39;, &#39;A&#39;]</span>
</pre></div>
</div>
<p>The <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></a> and <a class="reference internal" href="#bisect.insort" title="bisect.insort"><code class="xref py py-func docutils literal notranslate"><span class="pre">insort()</span></code></a> functions also work with lists of
tuples.  The <em>key</em> argument can serve to extract the field used for ordering
records in a table:</p>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">namedtuple</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">operator</span> <span class="kn">import</span> <span class="n">attrgetter</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">bisect</span> <span class="kn">import</span> <span class="n">bisect</span><span class="p">,</span> <span class="n">insort</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">pprint</span> <span class="kn">import</span> <span class="n">pprint</span>

<span class="gp">&gt;&gt;&gt; </span><span class="n">Movie</span> <span class="o">=</span> <span class="n">namedtuple</span><span class="p">(</span><span class="s1">&#39;Movie&#39;</span><span class="p">,</span> <span class="p">(</span><span class="s1">&#39;name&#39;</span><span class="p">,</span> <span class="s1">&#39;released&#39;</span><span class="p">,</span> <span class="s1">&#39;director&#39;</span><span class="p">))</span>

<span class="gp">&gt;&gt;&gt; </span><span class="n">movies</span> <span class="o">=</span> <span class="p">[</span>
<span class="gp">... </span>    <span class="n">Movie</span><span class="p">(</span><span class="s1">&#39;Jaws&#39;</span><span class="p">,</span> <span class="mi">1975</span><span class="p">,</span> <span class="s1">&#39;Speilberg&#39;</span><span class="p">),</span>
<span class="gp">... </span>    <span class="n">Movie</span><span class="p">(</span><span class="s1">&#39;Titanic&#39;</span><span class="p">,</span> <span class="mi">1997</span><span class="p">,</span> <span class="s1">&#39;Cameron&#39;</span><span class="p">),</span>
<span class="gp">... </span>    <span class="n">Movie</span><span class="p">(</span><span class="s1">&#39;The Birds&#39;</span><span class="p">,</span> <span class="mi">1963</span><span class="p">,</span> <span class="s1">&#39;Hitchcock&#39;</span><span class="p">),</span>
<span class="gp">... </span>    <span class="n">Movie</span><span class="p">(</span><span class="s1">&#39;Aliens&#39;</span><span class="p">,</span> <span class="mi">1986</span><span class="p">,</span> <span class="s1">&#39;Scott&#39;</span><span class="p">)</span>
<span class="gp">... </span><span class="p">]</span>

<span class="gp">&gt;&gt;&gt; </span><span class="c1"># Find the first movie released after 1960</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">by_year</span> <span class="o">=</span> <span class="n">attrgetter</span><span class="p">(</span><span class="s1">&#39;released&#39;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">movies</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="n">by_year</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">movies</span><span class="p">[</span><span class="n">bisect</span><span class="p">(</span><span class="n">movies</span><span class="p">,</span> <span class="mi">1960</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="n">by_year</span><span class="p">)]</span>
<span class="go">Movie(name=&#39;The Birds&#39;, released=1963, director=&#39;Hitchcock&#39;)</span>

<span class="gp">&gt;&gt;&gt; </span><span class="c1"># Insert a movie while maintaining sort order</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">romance</span> <span class="o">=</span> <span class="n">Movie</span><span class="p">(</span><span class="s1">&#39;Love Story&#39;</span><span class="p">,</span> <span class="mi">1970</span><span class="p">,</span> <span class="s1">&#39;Hiller&#39;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">insort</span><span class="p">(</span><span class="n">movies</span><span class="p">,</span> <span class="n">romance</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="n">by_year</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pprint</span><span class="p">(</span><span class="n">movies</span><span class="p">)</span>
<span class="go">[Movie(name=&#39;The Birds&#39;, released=1963, director=&#39;Hitchcock&#39;),</span>
<span class="go"> Movie(name=&#39;Love Story&#39;, released=1970, director=&#39;Hiller&#39;),</span>
<span class="go"> Movie(name=&#39;Jaws&#39;, released=1975, director=&#39;Speilberg&#39;),</span>
<span class="go"> Movie(name=&#39;Aliens&#39;, released=1986, director=&#39;Scott&#39;),</span>
<span class="go"> Movie(name=&#39;Titanic&#39;, released=1997, director=&#39;Cameron&#39;)]</span>
</pre></div>
</div>
<p>If the key function is expensive, it is possible to avoid repeated function
calls by searching a list of precomputed keys to find the index of a record:</p>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">data</span> <span class="o">=</span> <span class="p">[(</span><span class="s1">&#39;red&#39;</span><span class="p">,</span> <span class="mi">5</span><span class="p">),</span> <span class="p">(</span><span class="s1">&#39;blue&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="s1">&#39;yellow&#39;</span><span class="p">,</span> <span class="mi">8</span><span class="p">),</span> <span class="p">(</span><span class="s1">&#39;black&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span>
<span class="gp">&gt;&gt;&gt; </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="c1"># Or use operator.itemgetter(1).</span>
<span class="gp">&gt;&gt;&gt; </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="c1"># Precompute a list of keys.</span>
<span class="gp">&gt;&gt;&gt; </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">(&#39;black&#39;, 0)</span>
<span class="gp">&gt;&gt;&gt; </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">(&#39;blue&#39;, 1)</span>
<span class="gp">&gt;&gt;&gt; </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">(&#39;red&#39;, 5)</span>
<span class="gp">&gt;&gt;&gt; </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">(&#39;yellow&#39;, 8)</span>
</pre></div>
</div>
</section>
</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
  <h3><a href="../contents.html">Table of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#"><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a><ul>
<li><a class="reference internal" href="#performance-notes">Performance Notes</a></li>
<li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li>
<li><a class="reference internal" href="#examples">Examples</a></li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="heapq.html"
                        title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="array.html"
                        title="next chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">array</span></code> — Efficient arrays of numeric values</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../bugs.html">Report a Bug</a></li>
      <li>
        <a href="https://github.com/python/cpython/blob/3.10/Doc/library/bisect.rst"
            rel="nofollow">Show Source
        </a>
      </li>
    </ul>
  </div>
        </div>
      </div>
      <div class="clearer"></div>
    </div>  
    <div class="related" role="navigation" aria-label="related navigation">
      <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="array — Efficient arrays of numeric values"
             >next</a> |</li>
        <li class="right" >
          <a href="heapq.html" title="heapq — Heap queue algorithm"
             >previous</a> |</li>

          <li><img src="../_static/py.svg" alt="python logo" style="vertical-align: middle; margin-top: -1px"/></li>
          <li><a href="https://www.python.org/">Python</a> &#187;</li>
          <li class="switchers">
            <div class="language_switcher_placeholder"></div>
            <div class="version_switcher_placeholder"></div>
          </li>
          <li>
              
          </li>
    <li id="cpython-language-and-version">
      <a href="../index.html">3.10.12 Documentation</a> &#187;
    </li>

          <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="datatypes.html" >Data Types</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href=""><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a></li>
                <li class="right">
                    

    <div class="inline-search" role="search">
        <form class="inline-search" action="../search.html" method="get">
          <input placeholder="Quick search" aria-label="Quick search" 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>
    </div>
                     |
                </li>
            
      </ul>
    </div>  
    <div class="footer">
    &copy; <a href="../copyright.html">Copyright</a> 2001-2025, Python Software Foundation.
    <br />
    This page is licensed under the Python Software Foundation License Version 2.
    <br />
    Examples, recipes, and other code in the documentation are additionally licensed under the Zero Clause BSD License.
    <br />
    See <a href="/license.html">History and License</a> for more information.<br />
    <br />

    The Python Software Foundation is a non-profit corporation.
<a href="https://www.python.org/psf/donations/">Please donate.</a>
<br />
    <br />

    Last updated on August 15, 2025.
    <a href="/bugs.html">Found a bug</a>?
    <br />

    Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.3.2.
    </div>

  </body>
</html>
@ Telegram