parthtamu/rag-code-assistant
0
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 — 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> »</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> »185 </li>186 187 <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li>188 <li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">Data Types</a> »</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"><</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">>=</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"><=</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">></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">'Locate the leftmost value exactly equal to x'</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">'Find rightmost value less than x'</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">'Find rightmost value less than or equal to x'</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">'Find leftmost value greater than x'</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">'Find leftmost item greater than or equal to x'</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">>>> </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">"FDCBA"</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>399<span class="gp">...</span>400<span class="gp">>>> </span><span class="p">[</span><span class="n">grade</span><span class="p">(</span><span class="n">score</span><span class="p">)</span> <span class="k">for</span> <span class="n">score</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">33</span><span class="p">,</span> <span class="mi">99</span><span class="p">,</span> <span class="mi">77</span><span class="p">,</span> <span class="mi">70</span><span class="p">,</span> <span class="mi">89</span><span class="p">,</span> <span class="mi">90</span><span class="p">,</span> <span class="mi">100</span><span class="p">]]</span>401<span class="go">['F', 'A', 'C', 'C', 'B', 'A', 'A']</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">>>> </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">>>> </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">>>> </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">>>> </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">>>> </span><span class="n">Movie</span> <span class="o">=</span> <span class="n">namedtuple</span><span class="p">(</span><span class="s1">'Movie'</span><span class="p">,</span> <span class="p">(</span><span class="s1">'name'</span><span class="p">,</span> <span class="s1">'released'</span><span class="p">,</span> <span class="s1">'director'</span><span class="p">))</span>413 414<span class="gp">>>> </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">'Jaws'</span><span class="p">,</span> <span class="mi">1975</span><span class="p">,</span> <span class="s1">'Spielberg'</span><span class="p">),</span>416<span class="gp">... </span> <span class="n">Movie</span><span class="p">(</span><span class="s1">'Titanic'</span><span class="p">,</span> <span class="mi">1997</span><span class="p">,</span> <span class="s1">'Cameron'</span><span class="p">),</span>417<span class="gp">... </span> <span class="n">Movie</span><span class="p">(</span><span class="s1">'The Birds'</span><span class="p">,</span> <span class="mi">1963</span><span class="p">,</span> <span class="s1">'Hitchcock'</span><span class="p">),</span>418<span class="gp">... </span> <span class="n">Movie</span><span class="p">(</span><span class="s1">'Aliens'</span><span class="p">,</span> <span class="mi">1986</span><span class="p">,</span> <span class="s1">'Cameron'</span><span class="p">)</span>419<span class="gp">... </span><span class="p">]</span>420 421<span class="gp">>>> </span><span class="c1"># Find the first movie released after 1960</span>422<span class="gp">>>> </span><span class="n">by_year</span> <span class="o">=</span> <span class="n">attrgetter</span><span class="p">(</span><span class="s1">'released'</span><span class="p">)</span>423<span class="gp">>>> </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">>>> </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='The Birds', released=1963, director='Hitchcock')</span>426 427<span class="gp">>>> </span><span class="c1"># Insert a movie while maintaining sort order</span>428<span class="gp">>>> </span><span class="n">romance</span> <span class="o">=</span> <span class="n">Movie</span><span class="p">(</span><span class="s1">'Love Story'</span><span class="p">,</span> <span class="mi">1970</span><span class="p">,</span> <span class="s1">'Hiller'</span><span class="p">)</span>429<span class="gp">>>> </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">>>> </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='The Birds', released=1963, director='Hitchcock'),</span>432<span class="go"> Movie(name='Love Story', released=1970, director='Hiller'),</span>433<span class="go"> Movie(name='Jaws', released=1975, director='Spielberg'),</span>434<span class="go"> Movie(name='Aliens', released=1986, director='Cameron'),</span>435<span class="go"> Movie(name='Titanic', released=1997, director='Cameron')]</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">>>> </span><span class="n">data</span> <span class="o">=</span> <span class="p">[(</span><span class="s1">'red'</span><span class="p">,</span> <span class="mi">5</span><span class="p">),</span> <span class="p">(</span><span class="s1">'blue'</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="s1">'yellow'</span><span class="p">,</span> <span class="mi">8</span><span class="p">),</span> <span class="p">(</span><span class="s1">'black'</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span>441<span class="gp">>>> </span><span class="n">data</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">r</span><span class="p">:</span> <span class="n">r</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1"># Or use operator.itemgetter(1).</span>442<span class="gp">>>> </span><span class="n">keys</span> <span class="o">=</span> <span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="k">for</span> <span class="n">r</span> <span class="ow">in</span> <span class="n">data</span><span class="p">]</span> <span class="c1"># Precompute a list of keys.</span>443<span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span>444<span class="go">('black', 0)</span>445<span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">1</span><span class="p">)]</span>446<span class="go">('blue', 1)</span>447<span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">5</span><span class="p">)]</span>448<span class="go">('red', 5)</span>449<span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">8</span><span class="p">)]</span>450<span class="go">('yellow', 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> »</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> »547 </li>548 549 <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li>550 <li class="nav-item nav-item-2"><a href="datatypes.html" >Data Types</a> »</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 © <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>