Spaces:

parthtamu
/

rag-code-assistant

Sleeping

File size: 50,355 Bytes

dcac338

<!DOCTYPE html>

<html lang="en" data-content_root="../">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<meta property="og:title" content="bisect — Array bisection algorithm" />
<meta property="og:type" content="website" />
<meta property="og:url" content="https://docs.python.org/3/library/bisect.html" />
<meta property="og:site_name" content="Python documentation" />
<meta property="og:description" content="Source code: Lib/bisect.py 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 compariso..." />
<meta property="og:image:width" content="1146" />
<meta property="og:image:height" content="600" />
<meta property="og:image" content="https://docs.python.org/3.15/_images/social_previews/summary_library_bisect_f6bfc327.png" />
<meta property="og:image:alt" content="Source code: Lib/bisect.py 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 compariso..." />
<meta name="description" content="Source code: Lib/bisect.py 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 compariso..." />
<meta name="twitter:card" content="summary_large_image" />
<meta name="theme-color" content="#3776ab">

    <title>bisect — Array bisection algorithm &#8212; Python 3.15.0a6 documentation</title><meta name="viewport" content="width=device-width, initial-scale=1.0">
    
    <link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=b86133f3" />
    <link rel="stylesheet" type="text/css" href="../_static/classic.css?v=234b1a7c" />
    <link rel="stylesheet" type="text/css" href="../_static/pydoctheme.css?v=89a2f22a" />
    <link rel="stylesheet" type="text/css" href="../_static/profiling-sampling-visualization.css?v=0c2600ae" />
    <link id="pygments_dark_css" media="(prefers-color-scheme: dark)" rel="stylesheet" type="text/css" href="../_static/pygments_dark.css?v=5349f25f" />
    
    <script src="../_static/documentation_options.js?v=6b7c9ff5"></script>
    <script src="../_static/doctools.js?v=9bcbadda"></script>
    <script src="../_static/sphinx_highlight.js?v=dc90522c"></script>
    <script src="../_static/profiling-sampling-visualization.js?v=9811ed04"></script>
    
    <script src="../_static/sidebar.js"></script>
    
    <link rel="search" type="application/opensearchdescription+xml"
          title="Search within Python 3.15.0a6 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" />
    
      
      <script defer file-types="bz2,epub,zip" data-domain="docs.python.org" src="https://analytics.python.org/js/script.file-downloads.outbound-links.js"></script>
      
      <link rel="canonical" href="https://docs.python.org/3/library/bisect.html">
      
    

    
    <style>
      @media only screen {
        table.full-width-table {
            width: 100%;
        }
      }
    </style>
<link rel="stylesheet" href="../_static/pydoctheme_dark.css" media="(prefers-color-scheme: dark)" id="pydoctheme_dark_css">
    <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>
            <script type="text/javascript" src="../_static/search-focus.js"></script>
            <script type="text/javascript" src="../_static/themetoggle.js"></script> 
            <script type="text/javascript" src="../_static/rtd_switcher.js"></script>
            <meta name="readthedocs-addons-api-version" content="1">

  </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">
    <nav class="nav-content" role="navigation">
        <label for="menuToggler" class="toggler__label">
            <span></span>
        </label>
        <span class="nav-items-wrapper">
            <a href="https://www.python.org/" class="nav-logo">
                <img src="../_static/py.svg" alt="Python logo">
            </a>
            <span class="version_switcher_placeholder"></span>
            <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" fill="currentColor" 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"></path>
                </svg>
                <input placeholder="Quick search" aria-label="Quick search" type="search" name="q">
                <input type="submit" value="Go">
            </form>
        </span>
    </nav>
    <div class="menu-wrapper">
        <nav class="menu" role="navigation" aria-label="main navigation">
            <div class="language_switcher_placeholder"></div>
            
<label class="theme-selector-label">
    Theme
    <select class="theme-selector" oninput="activateTheme(this.value)">
        <option value="auto" selected>Auto</option>
        <option value="light">Light</option>
        <option value="dark">Dark</option>
    </select>
</label>
  <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>

  </div>
  <div>
    <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>
  </div>
  <div>
    <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>
  <script>
    document.addEventListener('DOMContentLoaded', () => {
        const title = document.querySelector('meta[property="og:title"]').content;
        const elements = document.querySelectorAll('.improvepage');
        const pageurl = window.location.href.split('?')[0];
        elements.forEach(element => {
            const url = new URL(element.href.split('?')[0].replace("-nojs", ""));
            url.searchParams.set('pagetitle', title);
            url.searchParams.set('pageurl', pageurl);
            url.searchParams.set('pagesource', "library/bisect.rst");
            element.href = url.toString();
        });
    });
  </script>
  <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 class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li>
      <li>
        <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1"
            rel="nofollow">Show source
        </a>
      </li>
      
    </ul>
  </div>
        </nav>
    </div>
</div>

  
    <div class="related" role="navigation" aria-label="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="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.15.0a6 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="search" name="q" id="search-box">
          <input type="submit" value="Go">
        </form>
    </div>
                     |
                </li>
            <li class="right">
<label class="theme-selector-label">
    Theme
    <select class="theme-selector" oninput="activateTheme(this.value)">
        <option value="auto" selected>Auto</option>
        <option value="light">Light</option>
        <option value="dark">Dark</option>
    </select>
</label> |</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><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm<a class="headerlink" href="#module-bisect" title="Link to this heading">¶</a></h1>
<p><strong>Source code:</strong> <a class="extlink-source reference external" href="https://github.com/python/cpython/tree/main/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
linear searches or frequent resorting.</p>
<p>The module is called <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> because it uses a basic bisection
algorithm to do its work.  Unlike other bisection tools that search for a
specific value, the functions in this module are designed to locate an
insertion point. Accordingly, the functions never call an <a class="reference internal" href="../reference/datamodel.html#object.__eq__" title="object.__eq__"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__eq__()</span></code></a>
method to determine whether a value has been found.  Instead, the
functions only call the <a class="reference internal" href="../reference/datamodel.html#object.__lt__" title="object.__lt__"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__lt__()</span></code></a> method and will return an insertion
point between values in an array.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>The functions in this module are not thread-safe. If multiple threads
concurrently use <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> functions on the same sequence, this
may result in undefined behaviour. Likewise, if the provided sequence
is mutated by a different thread while a <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> function
is operating on it, the result is undefined. For example, using
<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> on the same list from multiple threads
may result in the list becoming unsorted.</p>
</div>
<p id="bisect-functions">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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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>ip</em> partitions the array <em>a</em> into two
slices such that <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">&lt;</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[lo</span> <span class="pre">:</span> <span class="pre">ip])</span></code> is true for the
left slice and <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">&gt;=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[ip</span> <span class="pre">:</span> <span class="pre">hi])</span></code> is true for the
right slice.</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 and
no key function is called.</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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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>ip</em> partitions the array <em>a</em> into two slices
such that <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">&lt;=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[lo</span> <span class="pre">:</span> <span class="pre">ip])</span></code> is true for the left slice and
<code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">&gt;</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[ip</span> <span class="pre">:</span> <span class="pre">hi])</span></code> is true for the right slice.</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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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 <a class="reference internal" href="stdtypes.html#sequence.insert" title="sequence.insert"><code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code></a> 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 <em>O</em>(log <em>n</em>) search is dominated by the slow <em>O</em>(<em>n</em>)
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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></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="Link 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 <a class="reference internal" href="stdtypes.html#sequence.insert" title="sequence.insert"><code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code></a> 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 <em>O</em>(log <em>n</em>) search is dominated by the slow <em>O</em>(<em>n</em>)
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="Link to this heading">¶</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 <em>O</em>(<em>n</em>) 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="Link to this heading">¶</a></h2>
<p>The above <a class="reference internal" href="#bisect-functions">bisect functions</a> 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="w"> </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="w"> </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="w"> </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="w"> </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="w"> </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="Link to this heading">¶</a></h2>
<p id="bisect-example">The <a class="reference internal" href="#bisect.bisect" title="bisect.bisect"><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 <code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code> 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="w"> </span><span class="nf">grade</span><span class="p">(</span><span class="n">score</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="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">score</span><span class="p">)</span>
<span class="gp">... </span>    <span class="k">return</span> <span class="s2">&quot;FDCBA&quot;</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="#bisect.bisect" title="bisect.bisect"><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="w"> </span><span class="nn">collections</span><span class="w"> </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="w"> </span><span class="nn">operator</span><span class="w"> </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="w"> </span><span class="nn">bisect</span><span class="w"> </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="w"> </span><span class="nn">pprint</span><span class="w"> </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;Spielberg&#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;Cameron&#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;Spielberg&#39;),</span>
<span class="go"> Movie(name=&#39;Aliens&#39;, released=1986, director=&#39;Cameron&#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">
        <div class="sphinxsidebarwrapper">
  <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>

  </div>
  <div>
    <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>
  </div>
  <div>
    <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>
  <script>
    document.addEventListener('DOMContentLoaded', () => {
        const title = document.querySelector('meta[property="og:title"]').content;
        const elements = document.querySelectorAll('.improvepage');
        const pageurl = window.location.href.split('?')[0];
        elements.forEach(element => {
            const url = new URL(element.href.split('?')[0].replace("-nojs", ""));
            url.searchParams.set('pagetitle', title);
            url.searchParams.set('pageurl', pageurl);
            url.searchParams.set('pagesource', "library/bisect.rst");
            element.href = url.toString();
        });
    });
  </script>
  <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 class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li>
      <li>
        <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1"
            rel="nofollow">Show source
        </a>
      </li>
      
    </ul>
  </div>
        </div>
<div id="sidebarbutton" title="Collapse sidebar">
<span>«</span>
</div>

      </div>
      <div class="clearer"></div>
    </div>  
    <div class="related" role="navigation" aria-label="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="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.15.0a6 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="search" name="q" id="search-box">
          <input type="submit" value="Go">
        </form>
    </div>
                     |
                </li>
            <li class="right">
<label class="theme-selector-label">
    Theme
    <select class="theme-selector" oninput="activateTheme(this.value)">
        <option value="auto" selected>Auto</option>
        <option value="light">Light</option>
        <option value="dark">Dark</option>
    </select>
</label> |</li>
            
      </ul>
    </div>  
    <div class="footer">
    &copy; <a href="../copyright.html">Copyright</a> 2001 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 Mar 10, 2026 (08:58 UTC).
    
      <a href="/bugs.html">Found a bug</a>?
    
    <br>

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

  </body>
</html>