Team Ai
Apppublic

parthtamu/rag-code-assistant

sourceHugging Faceupdated 7mo agoView on Hugging Face
0likes
bisect.html602 linesDownload Raw Back to docs
1<!DOCTYPE html>2 3<html lang="en" data-content_root="../">4  <head>5    <meta charset="utf-8" />6    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />7<meta property="og:title" content="bisect — Array bisection algorithm" />8<meta property="og:type" content="website" />9<meta property="og:url" content="https://docs.python.org/3/library/bisect.html" />10<meta property="og:site_name" content="Python documentation" />11<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..." />12<meta property="og:image:width" content="1146" />13<meta property="og:image:height" content="600" />14<meta property="og:image" content="https://docs.python.org/3.15/_images/social_previews/summary_library_bisect_f6bfc327.png" />15<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..." />16<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..." />17<meta name="twitter:card" content="summary_large_image" />18<meta name="theme-color" content="#3776ab">19 20    <title>bisect — Array bisection algorithm &#8212; Python 3.15.0a6 documentation</title><meta name="viewport" content="width=device-width, initial-scale=1.0">21    22    <link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=b86133f3" />23    <link rel="stylesheet" type="text/css" href="../_static/classic.css?v=234b1a7c" />24    <link rel="stylesheet" type="text/css" href="../_static/pydoctheme.css?v=89a2f22a" />25    <link rel="stylesheet" type="text/css" href="../_static/profiling-sampling-visualization.css?v=0c2600ae" />26    <link id="pygments_dark_css" media="(prefers-color-scheme: dark)" rel="stylesheet" type="text/css" href="../_static/pygments_dark.css?v=5349f25f" />27    28    <script src="../_static/documentation_options.js?v=6b7c9ff5"></script>29    <script src="../_static/doctools.js?v=9bcbadda"></script>30    <script src="../_static/sphinx_highlight.js?v=dc90522c"></script>31    <script src="../_static/profiling-sampling-visualization.js?v=9811ed04"></script>32    33    <script src="../_static/sidebar.js"></script>34    35    <link rel="search" type="application/opensearchdescription+xml"36          title="Search within Python 3.15.0a6 documentation"37          href="../_static/opensearch.xml"/>38    <link rel="author" title="About these documents" href="../about.html" />39    <link rel="index" title="Index" href="../genindex.html" />40    <link rel="search" title="Search" href="../search.html" />41    <link rel="copyright" title="Copyright" href="../copyright.html" />42    <link rel="next" title="array — Efficient arrays of numeric values" href="array.html" />43    <link rel="prev" title="heapq — Heap queue algorithm" href="heapq.html" />44    45      46      <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>47      48      <link rel="canonical" href="https://docs.python.org/3/library/bisect.html">49      50    51 52    53    <style>54      @media only screen {55        table.full-width-table {56            width: 100%;57        }58      }59    </style>60<link rel="stylesheet" href="../_static/pydoctheme_dark.css" media="(prefers-color-scheme: dark)" id="pydoctheme_dark_css">61    <link rel="shortcut icon" type="image/png" href="../_static/py.svg">62            <script type="text/javascript" src="../_static/copybutton.js"></script>63            <script type="text/javascript" src="../_static/menu.js"></script>64            <script type="text/javascript" src="../_static/search-focus.js"></script>65            <script type="text/javascript" src="../_static/themetoggle.js"></script> 66            <script type="text/javascript" src="../_static/rtd_switcher.js"></script>67            <meta name="readthedocs-addons-api-version" content="1">68 69  </head>70<body>71<div class="mobile-nav">72    <input type="checkbox" id="menuToggler" class="toggler__input" aria-controls="navigation"73           aria-pressed="false" aria-expanded="false" role="button" aria-label="Menu">74    <nav class="nav-content" role="navigation">75        <label for="menuToggler" class="toggler__label">76            <span></span>77        </label>78        <span class="nav-items-wrapper">79            <a href="https://www.python.org/" class="nav-logo">80                <img src="../_static/py.svg" alt="Python logo">81            </a>82            <span class="version_switcher_placeholder"></span>83            <form role="search" class="search" action="../search.html" method="get">84                <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" viewBox="0 0 24 24" class="search-icon">85                    <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>86                </svg>87                <input placeholder="Quick search" aria-label="Quick search" type="search" name="q">88                <input type="submit" value="Go">89            </form>90        </span>91    </nav>92    <div class="menu-wrapper">93        <nav class="menu" role="navigation" aria-label="main navigation">94            <div class="language_switcher_placeholder"></div>95            96<label class="theme-selector-label">97    Theme98    <select class="theme-selector" oninput="activateTheme(this.value)">99        <option value="auto" selected>Auto</option>100        <option value="light">Light</option>101        <option value="dark">Dark</option>102    </select>103</label>104  <div>105    <h3><a href="../contents.html">Table of Contents</a></h3>106    <ul>107<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>108<li><a class="reference internal" href="#performance-notes">Performance Notes</a></li>109<li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li>110<li><a class="reference internal" href="#examples">Examples</a></li>111</ul>112</li>113</ul>114 115  </div>116  <div>117    <h4>Previous topic</h4>118    <p class="topless"><a href="heapq.html"119                          title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p>120  </div>121  <div>122    <h4>Next topic</h4>123    <p class="topless"><a href="array.html"124                          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>125  </div>126  <script>127    document.addEventListener('DOMContentLoaded', () => {128        const title = document.querySelector('meta[property="og:title"]').content;129        const elements = document.querySelectorAll('.improvepage');130        const pageurl = window.location.href.split('?')[0];131        elements.forEach(element => {132            const url = new URL(element.href.split('?')[0].replace("-nojs", ""));133            url.searchParams.set('pagetitle', title);134            url.searchParams.set('pageurl', pageurl);135            url.searchParams.set('pagesource', "library/bisect.rst");136            element.href = url.toString();137        });138    });139  </script>140  <div role="note" aria-label="source link">141    <h3>This page</h3>142    <ul class="this-page-menu">143      <li><a href="../bugs.html">Report a bug</a></li>144      <li><a class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li>145      <li>146        <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1"147            rel="nofollow">Show source148        </a>149      </li>150      151    </ul>152  </div>153        </nav>154    </div>155</div>156 157  158    <div class="related" role="navigation" aria-label="Related">159      <h3>Navigation</h3>160      <ul>161        <li class="right" style="margin-right: 10px">162          <a href="../genindex.html" title="General Index"163             accesskey="I">index</a></li>164        <li class="right" >165          <a href="../py-modindex.html" title="Python Module Index"166             >modules</a> |</li>167        <li class="right" >168          <a href="array.html" title="array — Efficient arrays of numeric values"169             accesskey="N">next</a> |</li>170        <li class="right" >171          <a href="heapq.html" title="heapq — Heap queue algorithm"172             accesskey="P">previous</a> |</li>173 174          <li><img src="../_static/py.svg" alt="Python logo" style="vertical-align: middle; margin-top: -1px"></li>175          <li><a href="https://www.python.org/">Python</a> &#187;</li>176          <li class="switchers">177            <div class="language_switcher_placeholder"></div>178            <div class="version_switcher_placeholder"></div>179          </li>180          <li>181              182          </li>183    <li id="cpython-language-and-version">184      <a href="../index.html">3.15.0a6 Documentation</a> &#187;185    </li>186 187          <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> &#187;</li>188          <li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">Data Types</a> &#187;</li>189        <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>190                <li class="right">191                    192 193    <div class="inline-search" role="search">194        <form class="inline-search" action="../search.html" method="get">195          <input placeholder="Quick search" aria-label="Quick search" type="search" name="q" id="search-box">196          <input type="submit" value="Go">197        </form>198    </div>199                     |200                </li>201            <li class="right">202<label class="theme-selector-label">203    Theme204    <select class="theme-selector" oninput="activateTheme(this.value)">205        <option value="auto" selected>Auto</option>206        <option value="light">Light</option>207        <option value="dark">Dark</option>208    </select>209</label> |</li>210            211      </ul>212    </div>    213 214    <div class="document">215      <div class="documentwrapper">216        <div class="bodywrapper">217          <div class="body" role="main">218            219  <section id="module-bisect">220<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>221<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>222<hr class="docutils" />223<p>This module provides support for maintaining a list in sorted order without224having to sort the list after each insertion.  For long lists of items with225expensive comparison operations, this can be an improvement over226linear searches or frequent resorting.</p>227<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 bisection228algorithm to do its work.  Unlike other bisection tools that search for a229specific value, the functions in this module are designed to locate an230insertion 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>231method to determine whether a value has been found.  Instead, the232functions 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 insertion233point between values in an array.</p>234<div class="admonition note">235<p class="admonition-title">Note</p>236<p>The functions in this module are not thread-safe. If multiple threads237concurrently use <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> functions on the same sequence, this238may result in undefined behaviour. Likewise, if the provided sequence239is mutated by a different thread while a <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> function240is operating on it, the result is undefined. For example, using241<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 threads242may result in the list becoming unsorted.</p>243</div>244<p id="bisect-functions">The following functions are provided:</p>245<dl class="py function">246<dt class="sig sig-object py" id="bisect.bisect_left">247<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>248<dd><p>Locate the insertion point for <em>x</em> in <em>a</em> to maintain sorted order.249The parameters <em>lo</em> and <em>hi</em> may be used to specify a subset of the list250which should be considered; by default the entire list is used.  If <em>x</em> is251already present in <em>a</em>, the insertion point will be before (to the left of)252any existing entries.  The return value is suitable for use as the first253parameter to <code class="docutils literal notranslate"><span class="pre">list.insert()</span></code> assuming that <em>a</em> is already sorted.</p>254<p>The returned insertion point <em>ip</em> partitions the array <em>a</em> into two255slices 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 the256left 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 the257right slice.</p>258<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 to259extract a comparison key from each element in the array.  To support260searching complex records, the key function is not applied to the <em>x</em> value.</p>261<p>If <em>key</em> is <code class="docutils literal notranslate"><span class="pre">None</span></code>, the elements are compared directly and262no key function is called.</p>263<div class="versionchanged">264<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>265</div>266</dd></dl>267 268<dl class="py function">269<dt class="sig sig-object py" id="bisect.bisect_right">270<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>271<dt class="sig sig-object py" id="bisect.bisect">272<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>273<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 comes274after (to the right of) any existing entries of <em>x</em> in <em>a</em>.</p>275<p>The returned insertion point <em>ip</em> partitions the array <em>a</em> into two slices276such 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 and277<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>278<div class="versionchanged">279<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>280</div>281</dd></dl>282 283<dl class="py function">284<dt class="sig sig-object py" id="bisect.insort_left">285<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>286<dd><p>Insert <em>x</em> in <em>a</em> in sorted order.</p>287<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.288Next, 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 the289appropriate position to maintain sort order.</p>290<p>To support inserting records in a table, the <em>key</em> function (if any) is291applied to <em>x</em> for the search step but not for the insertion step.</p>292<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>)293insertion step.</p>294<div class="versionchanged">295<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>296</div>297</dd></dl>298 299<dl class="py function">300<dt class="sig sig-object py" id="bisect.insort_right">301<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>302<dt class="sig sig-object py" id="bisect.insort">303<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>304<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 existing305entries of <em>x</em>.</p>306<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.307Next, 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 the308appropriate position to maintain sort order.</p>309<p>To support inserting records in a table, the <em>key</em> function (if any) is310applied to <em>x</em> for the search step but not for the insertion step.</p>311<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>)312insertion step.</p>313<div class="versionchanged">314<p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p>315</div>316</dd></dl>317 318<section id="performance-notes">319<h2>Performance Notes<a class="headerlink" href="#performance-notes" title="Link to this heading">¶</a></h2>320<p>When writing time sensitive code using <em>bisect()</em> and <em>insort()</em>, keep these321thoughts in mind:</p>322<ul class="simple">323<li><p>Bisection is effective for searching ranges of values.324For locating specific values, dictionaries are more performant.</p></li>325<li><p>The <em>insort()</em> functions are <em>O</em>(<em>n</em>) because the logarithmic search step326is dominated by the linear time insertion step.</p></li>327<li><p>The search functions are stateless and discard key function results after328they are used.  Consequently, if the search functions are used in a loop,329the key function may be called again and again on the same array elements.330If the key function isn’t fast, consider wrapping it with331<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,332consider searching an array of precomputed keys to locate the insertion333point (as shown in the examples section below).</p></li>334</ul>335<div class="admonition seealso">336<p class="admonition-title">See also</p>337<ul class="simple">338<li><p><a class="reference external" href="https://grantjenks.com/docs/sortedcollections/">Sorted Collections</a> is a high performance339module that uses <em>bisect</em> to managed sorted collections of data.</p></li>340<li><p>The <a class="reference external" href="https://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> uses341bisect to build a full-featured collection class with straight-forward search342methods and support for a key-function.  The keys are precomputed to save343unnecessary calls to the key function during searches.</p></li>344</ul>345</div>346</section>347<section id="searching-sorted-lists">348<h2>Searching Sorted Lists<a class="headerlink" href="#searching-sorted-lists" title="Link to this heading">¶</a></h2>349<p>The above <a class="reference internal" href="#bisect-functions">bisect functions</a> are useful for finding insertion points but350can be tricky or awkward to use for common searching tasks. The following five351functions show how to transform them into the standard lookups for sorted352lists:</p>353<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>354    <span class="s1">&#39;Locate the leftmost value exactly equal to x&#39;</span>355    <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>356    <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>357        <span class="k">return</span> <span class="n">i</span>358    <span class="k">raise</span> <span class="ne">ValueError</span>359 360<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>361    <span class="s1">&#39;Find rightmost value less than x&#39;</span>362    <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>363    <span class="k">if</span> <span class="n">i</span><span class="p">:</span>364        <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>365    <span class="k">raise</span> <span class="ne">ValueError</span>366 367<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>368    <span class="s1">&#39;Find rightmost value less than or equal to x&#39;</span>369    <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>370    <span class="k">if</span> <span class="n">i</span><span class="p">:</span>371        <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>372    <span class="k">raise</span> <span class="ne">ValueError</span>373 374<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>375    <span class="s1">&#39;Find leftmost value greater than x&#39;</span>376    <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>377    <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>378        <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>379    <span class="k">raise</span> <span class="ne">ValueError</span>380 381<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>382    <span class="s1">&#39;Find leftmost item greater than or equal to x&#39;</span>383    <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>384    <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>385        <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>386    <span class="k">raise</span> <span class="ne">ValueError</span>387</pre></div>388</div>389</section>390<section id="examples">391<h2>Examples<a class="headerlink" href="#examples" title="Link to this heading">¶</a></h2>392<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. This393example 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)394based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is395a ‘B’, and so on:</p>396<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>397<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>398<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>399<span class="gp">...</span>400<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>401<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>402</pre></div>403</div>404<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 with405lists of tuples.  The <em>key</em> argument can serve to extract the field used for ordering406records in a table:</p>407<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>408<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>409<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>410<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>411 412<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>413 414<span class="gp">&gt;&gt;&gt; </span><span class="n">movies</span> <span class="o">=</span> <span class="p">[</span>415<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>416<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>417<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>418<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>419<span class="gp">... </span><span class="p">]</span>420 421<span class="gp">&gt;&gt;&gt; </span><span class="c1"># Find the first movie released after 1960</span>422<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>423<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>424<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>425<span class="go">Movie(name=&#39;The Birds&#39;, released=1963, director=&#39;Hitchcock&#39;)</span>426 427<span class="gp">&gt;&gt;&gt; </span><span class="c1"># Insert a movie while maintaining sort order</span>428<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>429<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>430<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>431<span class="go">[Movie(name=&#39;The Birds&#39;, released=1963, director=&#39;Hitchcock&#39;),</span>432<span class="go"> Movie(name=&#39;Love Story&#39;, released=1970, director=&#39;Hiller&#39;),</span>433<span class="go"> Movie(name=&#39;Jaws&#39;, released=1975, director=&#39;Spielberg&#39;),</span>434<span class="go"> Movie(name=&#39;Aliens&#39;, released=1986, director=&#39;Cameron&#39;),</span>435<span class="go"> Movie(name=&#39;Titanic&#39;, released=1997, director=&#39;Cameron&#39;)]</span>436</pre></div>437</div>438<p>If the key function is expensive, it is possible to avoid repeated function439calls by searching a list of precomputed keys to find the index of a record:</p>440<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>441<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>442<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>443<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>444<span class="go">(&#39;black&#39;, 0)</span>445<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>446<span class="go">(&#39;blue&#39;, 1)</span>447<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>448<span class="go">(&#39;red&#39;, 5)</span>449<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>450<span class="go">(&#39;yellow&#39;, 8)</span>451</pre></div>452</div>453</section>454</section>455 456 457            <div class="clearer"></div>458          </div>459        </div>460      </div>461      <div class="sphinxsidebar" role="navigation" aria-label="Main">462        <div class="sphinxsidebarwrapper">463  <div>464    <h3><a href="../contents.html">Table of Contents</a></h3>465    <ul>466<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>467<li><a class="reference internal" href="#performance-notes">Performance Notes</a></li>468<li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li>469<li><a class="reference internal" href="#examples">Examples</a></li>470</ul>471</li>472</ul>473 474  </div>475  <div>476    <h4>Previous topic</h4>477    <p class="topless"><a href="heapq.html"478                          title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p>479  </div>480  <div>481    <h4>Next topic</h4>482    <p class="topless"><a href="array.html"483                          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>484  </div>485  <script>486    document.addEventListener('DOMContentLoaded', () => {487        const title = document.querySelector('meta[property="og:title"]').content;488        const elements = document.querySelectorAll('.improvepage');489        const pageurl = window.location.href.split('?')[0];490        elements.forEach(element => {491            const url = new URL(element.href.split('?')[0].replace("-nojs", ""));492            url.searchParams.set('pagetitle', title);493            url.searchParams.set('pageurl', pageurl);494            url.searchParams.set('pagesource', "library/bisect.rst");495            element.href = url.toString();496        });497    });498  </script>499  <div role="note" aria-label="source link">500    <h3>This page</h3>501    <ul class="this-page-menu">502      <li><a href="../bugs.html">Report a bug</a></li>503      <li><a class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li>504      <li>505        <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1"506            rel="nofollow">Show source507        </a>508      </li>509      510    </ul>511  </div>512        </div>513<div id="sidebarbutton" title="Collapse sidebar">514<span>«</span>515</div>516 517      </div>518      <div class="clearer"></div>519    </div>  520    <div class="related" role="navigation" aria-label="Related">521      <h3>Navigation</h3>522      <ul>523        <li class="right" style="margin-right: 10px">524          <a href="../genindex.html" title="General Index"525             >index</a></li>526        <li class="right" >527          <a href="../py-modindex.html" title="Python Module Index"528             >modules</a> |</li>529        <li class="right" >530          <a href="array.html" title="array — Efficient arrays of numeric values"531             >next</a> |</li>532        <li class="right" >533          <a href="heapq.html" title="heapq — Heap queue algorithm"534             >previous</a> |</li>535 536          <li><img src="../_static/py.svg" alt="Python logo" style="vertical-align: middle; margin-top: -1px"></li>537          <li><a href="https://www.python.org/">Python</a> &#187;</li>538          <li class="switchers">539            <div class="language_switcher_placeholder"></div>540            <div class="version_switcher_placeholder"></div>541          </li>542          <li>543              544          </li>545    <li id="cpython-language-and-version">546      <a href="../index.html">3.15.0a6 Documentation</a> &#187;547    </li>548 549          <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> &#187;</li>550          <li class="nav-item nav-item-2"><a href="datatypes.html" >Data Types</a> &#187;</li>551        <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>552                <li class="right">553                    554 555    <div class="inline-search" role="search">556        <form class="inline-search" action="../search.html" method="get">557          <input placeholder="Quick search" aria-label="Quick search" type="search" name="q" id="search-box">558          <input type="submit" value="Go">559        </form>560    </div>561                     |562                </li>563            <li class="right">564<label class="theme-selector-label">565    Theme566    <select class="theme-selector" oninput="activateTheme(this.value)">567        <option value="auto" selected>Auto</option>568        <option value="light">Light</option>569        <option value="dark">Dark</option>570    </select>571</label> |</li>572            573      </ul>574    </div>  575    <div class="footer">576    &copy; <a href="../copyright.html">Copyright</a> 2001 Python Software Foundation.577    <br>578    This page is licensed under the Python Software Foundation License Version 2.579    <br>580    Examples, recipes, and other code in the documentation are additionally licensed under the Zero Clause BSD License.581    <br>582    583      See <a href="/license.html">History and License</a> for more information.<br>584    585    586    <br>587 588    The Python Software Foundation is a non-profit corporation.589<a href="https://www.python.org/psf/donations/">Please donate.</a>590<br>591    <br>592      Last updated on Mar 10, 2026 (08:58 UTC).593    594      <a href="/bugs.html">Found a bug</a>?595    596    <br>597 598    Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 8.2.3.599    </div>600 601  </body>602</html>