Spaces:
Sleeping
Sleeping
| <html lang="en" data-content_root="../"> | |
| <head> | |
| <meta charset="utf-8" /> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" /> | |
| <meta property="og:title" content="bisect — Array bisection algorithm" /> | |
| <meta property="og:type" content="website" /> | |
| <meta property="og:url" content="https://docs.python.org/3/library/bisect.html" /> | |
| <meta property="og:site_name" content="Python documentation" /> | |
| <meta property="og:description" content="Source code: Lib/bisect.py This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive compariso..." /> | |
| <meta property="og:image:width" content="1146" /> | |
| <meta property="og:image:height" content="600" /> | |
| <meta property="og:image" content="https://docs.python.org/3.15/_images/social_previews/summary_library_bisect_f6bfc327.png" /> | |
| <meta property="og:image:alt" content="Source code: Lib/bisect.py This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive compariso..." /> | |
| <meta name="description" content="Source code: Lib/bisect.py This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive compariso..." /> | |
| <meta name="twitter:card" content="summary_large_image" /> | |
| <meta name="theme-color" content="#3776ab"> | |
| <title>bisect — Array bisection algorithm — Python 3.15.0a6 documentation</title><meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=b86133f3" /> | |
| <link rel="stylesheet" type="text/css" href="../_static/classic.css?v=234b1a7c" /> | |
| <link rel="stylesheet" type="text/css" href="../_static/pydoctheme.css?v=89a2f22a" /> | |
| <link rel="stylesheet" type="text/css" href="../_static/profiling-sampling-visualization.css?v=0c2600ae" /> | |
| <link id="pygments_dark_css" media="(prefers-color-scheme: dark)" rel="stylesheet" type="text/css" href="../_static/pygments_dark.css?v=5349f25f" /> | |
| <script src="../_static/documentation_options.js?v=6b7c9ff5"></script> | |
| <script src="../_static/doctools.js?v=9bcbadda"></script> | |
| <script src="../_static/sphinx_highlight.js?v=dc90522c"></script> | |
| <script src="../_static/profiling-sampling-visualization.js?v=9811ed04"></script> | |
| <script src="../_static/sidebar.js"></script> | |
| <link rel="search" type="application/opensearchdescription+xml" | |
| title="Search within Python 3.15.0a6 documentation" | |
| href="../_static/opensearch.xml"/> | |
| <link rel="author" title="About these documents" href="../about.html" /> | |
| <link rel="index" title="Index" href="../genindex.html" /> | |
| <link rel="search" title="Search" href="../search.html" /> | |
| <link rel="copyright" title="Copyright" href="../copyright.html" /> | |
| <link rel="next" title="array — Efficient arrays of numeric values" href="array.html" /> | |
| <link rel="prev" title="heapq — Heap queue algorithm" href="heapq.html" /> | |
| <script defer file-types="bz2,epub,zip" data-domain="docs.python.org" src="https://analytics.python.org/js/script.file-downloads.outbound-links.js"></script> | |
| <link rel="canonical" href="https://docs.python.org/3/library/bisect.html"> | |
| <style> | |
| @media only screen { | |
| table.full-width-table { | |
| width: 100%; | |
| } | |
| } | |
| </style> | |
| <link rel="stylesheet" href="../_static/pydoctheme_dark.css" media="(prefers-color-scheme: dark)" id="pydoctheme_dark_css"> | |
| <link rel="shortcut icon" type="image/png" href="../_static/py.svg"> | |
| <script type="text/javascript" src="../_static/copybutton.js"></script> | |
| <script type="text/javascript" src="../_static/menu.js"></script> | |
| <script type="text/javascript" src="../_static/search-focus.js"></script> | |
| <script type="text/javascript" src="../_static/themetoggle.js"></script> | |
| <script type="text/javascript" src="../_static/rtd_switcher.js"></script> | |
| <meta name="readthedocs-addons-api-version" content="1"> | |
| </head> | |
| <body> | |
| <div class="mobile-nav"> | |
| <input type="checkbox" id="menuToggler" class="toggler__input" aria-controls="navigation" | |
| aria-pressed="false" aria-expanded="false" role="button" aria-label="Menu"> | |
| <nav class="nav-content" role="navigation"> | |
| <label for="menuToggler" class="toggler__label"> | |
| <span></span> | |
| </label> | |
| <span class="nav-items-wrapper"> | |
| <a href="https://www.python.org/" class="nav-logo"> | |
| <img src="../_static/py.svg" alt="Python logo"> | |
| </a> | |
| <span class="version_switcher_placeholder"></span> | |
| <form role="search" class="search" action="../search.html" method="get"> | |
| <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" viewBox="0 0 24 24" class="search-icon"> | |
| <path fill-rule="nonzero" fill="currentColor" d="M15.5 14h-.79l-.28-.27a6.5 6.5 0 001.48-5.34c-.47-2.78-2.79-5-5.59-5.34a6.505 6.505 0 00-7.27 7.27c.34 2.8 2.56 5.12 5.34 5.59a6.5 6.5 0 005.34-1.48l.27.28v.79l4.25 4.25c.41.41 1.08.41 1.49 0 .41-.41.41-1.08 0-1.49L15.5 14zm-6 0C7.01 14 5 11.99 5 9.5S7.01 5 9.5 5 14 7.01 14 9.5 11.99 14 9.5 14z"></path> | |
| </svg> | |
| <input placeholder="Quick search" aria-label="Quick search" type="search" name="q"> | |
| <input type="submit" value="Go"> | |
| </form> | |
| </span> | |
| </nav> | |
| <div class="menu-wrapper"> | |
| <nav class="menu" role="navigation" aria-label="main navigation"> | |
| <div class="language_switcher_placeholder"></div> | |
| <label class="theme-selector-label"> | |
| Theme | |
| <select class="theme-selector" oninput="activateTheme(this.value)"> | |
| <option value="auto" selected>Auto</option> | |
| <option value="light">Light</option> | |
| <option value="dark">Dark</option> | |
| </select> | |
| </label> | |
| <div> | |
| <h3><a href="../contents.html">Table of Contents</a></h3> | |
| <ul> | |
| <li><a class="reference internal" href="#"><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a><ul> | |
| <li><a class="reference internal" href="#performance-notes">Performance Notes</a></li> | |
| <li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li> | |
| <li><a class="reference internal" href="#examples">Examples</a></li> | |
| </ul> | |
| </li> | |
| </ul> | |
| </div> | |
| <div> | |
| <h4>Previous topic</h4> | |
| <p class="topless"><a href="heapq.html" | |
| title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p> | |
| </div> | |
| <div> | |
| <h4>Next topic</h4> | |
| <p class="topless"><a href="array.html" | |
| title="next chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">array</span></code> — Efficient arrays of numeric values</a></p> | |
| </div> | |
| <script> | |
| document.addEventListener('DOMContentLoaded', () => { | |
| const title = document.querySelector('meta[property="og:title"]').content; | |
| const elements = document.querySelectorAll('.improvepage'); | |
| const pageurl = window.location.href.split('?')[0]; | |
| elements.forEach(element => { | |
| const url = new URL(element.href.split('?')[0].replace("-nojs", "")); | |
| url.searchParams.set('pagetitle', title); | |
| url.searchParams.set('pageurl', pageurl); | |
| url.searchParams.set('pagesource', "library/bisect.rst"); | |
| element.href = url.toString(); | |
| }); | |
| }); | |
| </script> | |
| <div role="note" aria-label="source link"> | |
| <h3>This page</h3> | |
| <ul class="this-page-menu"> | |
| <li><a href="../bugs.html">Report a bug</a></li> | |
| <li><a class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li> | |
| <li> | |
| <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1" | |
| rel="nofollow">Show source | |
| </a> | |
| </li> | |
| </ul> | |
| </div> | |
| </nav> | |
| </div> | |
| </div> | |
| <div class="related" role="navigation" aria-label="Related"> | |
| <h3>Navigation</h3> | |
| <ul> | |
| <li class="right" style="margin-right: 10px"> | |
| <a href="../genindex.html" title="General Index" | |
| accesskey="I">index</a></li> | |
| <li class="right" > | |
| <a href="../py-modindex.html" title="Python Module Index" | |
| >modules</a> |</li> | |
| <li class="right" > | |
| <a href="array.html" title="array — Efficient arrays of numeric values" | |
| accesskey="N">next</a> |</li> | |
| <li class="right" > | |
| <a href="heapq.html" title="heapq — Heap queue algorithm" | |
| accesskey="P">previous</a> |</li> | |
| <li><img src="../_static/py.svg" alt="Python logo" style="vertical-align: middle; margin-top: -1px"></li> | |
| <li><a href="https://www.python.org/">Python</a> »</li> | |
| <li class="switchers"> | |
| <div class="language_switcher_placeholder"></div> | |
| <div class="version_switcher_placeholder"></div> | |
| </li> | |
| <li> | |
| </li> | |
| <li id="cpython-language-and-version"> | |
| <a href="../index.html">3.15.0a6 Documentation</a> » | |
| </li> | |
| <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li> | |
| <li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">Data Types</a> »</li> | |
| <li class="nav-item nav-item-this"><a href=""><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a></li> | |
| <li class="right"> | |
| <div class="inline-search" role="search"> | |
| <form class="inline-search" action="../search.html" method="get"> | |
| <input placeholder="Quick search" aria-label="Quick search" type="search" name="q" id="search-box"> | |
| <input type="submit" value="Go"> | |
| </form> | |
| </div> | |
| | | |
| </li> | |
| <li class="right"> | |
| <label class="theme-selector-label"> | |
| Theme | |
| <select class="theme-selector" oninput="activateTheme(this.value)"> | |
| <option value="auto" selected>Auto</option> | |
| <option value="light">Light</option> | |
| <option value="dark">Dark</option> | |
| </select> | |
| </label> |</li> | |
| </ul> | |
| </div> | |
| <div class="document"> | |
| <div class="documentwrapper"> | |
| <div class="bodywrapper"> | |
| <div class="body" role="main"> | |
| <section id="module-bisect"> | |
| <span id="bisect-array-bisection-algorithm"></span><h1><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm<a class="headerlink" href="#module-bisect" title="Link to this heading">¶</a></h1> | |
| <p><strong>Source code:</strong> <a class="extlink-source reference external" href="https://github.com/python/cpython/tree/main/Lib/bisect.py">Lib/bisect.py</a></p> | |
| <hr class="docutils" /> | |
| <p>This module provides support for maintaining a list in sorted order without | |
| having to sort the list after each insertion. For long lists of items with | |
| expensive comparison operations, this can be an improvement over | |
| linear searches or frequent resorting.</p> | |
| <p>The module is called <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> because it uses a basic bisection | |
| algorithm to do its work. Unlike other bisection tools that search for a | |
| specific value, the functions in this module are designed to locate an | |
| insertion point. Accordingly, the functions never call an <a class="reference internal" href="../reference/datamodel.html#object.__eq__" title="object.__eq__"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__eq__()</span></code></a> | |
| method to determine whether a value has been found. Instead, the | |
| functions only call the <a class="reference internal" href="../reference/datamodel.html#object.__lt__" title="object.__lt__"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__lt__()</span></code></a> method and will return an insertion | |
| point between values in an array.</p> | |
| <div class="admonition note"> | |
| <p class="admonition-title">Note</p> | |
| <p>The functions in this module are not thread-safe. If multiple threads | |
| concurrently use <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> functions on the same sequence, this | |
| may result in undefined behaviour. Likewise, if the provided sequence | |
| is mutated by a different thread while a <code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> function | |
| is operating on it, the result is undefined. For example, using | |
| <a class="reference internal" href="#bisect.insort_left" title="bisect.insort_left"><code class="xref py py-func docutils literal notranslate"><span class="pre">insort_left()</span></code></a> on the same list from multiple threads | |
| may result in the list becoming unsorted.</p> | |
| </div> | |
| <p id="bisect-functions">The following functions are provided:</p> | |
| <dl class="py function"> | |
| <dt class="sig sig-object py" id="bisect.bisect_left"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect_left</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.bisect_left" title="Link to this definition">¶</a></dt> | |
| <dd><p>Locate the insertion point for <em>x</em> in <em>a</em> to maintain sorted order. | |
| The parameters <em>lo</em> and <em>hi</em> may be used to specify a subset of the list | |
| which should be considered; by default the entire list is used. If <em>x</em> is | |
| already present in <em>a</em>, the insertion point will be before (to the left of) | |
| any existing entries. The return value is suitable for use as the first | |
| parameter to <code class="docutils literal notranslate"><span class="pre">list.insert()</span></code> assuming that <em>a</em> is already sorted.</p> | |
| <p>The returned insertion point <em>ip</em> partitions the array <em>a</em> into two | |
| slices such that <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre"><</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[lo</span> <span class="pre">:</span> <span class="pre">ip])</span></code> is true for the | |
| left slice and <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">>=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[ip</span> <span class="pre">:</span> <span class="pre">hi])</span></code> is true for the | |
| right slice.</p> | |
| <p><em>key</em> specifies a <a class="reference internal" href="../glossary.html#term-key-function"><span class="xref std std-term">key function</span></a> of one argument that is used to | |
| extract a comparison key from each element in the array. To support | |
| searching complex records, the key function is not applied to the <em>x</em> value.</p> | |
| <p>If <em>key</em> is <code class="docutils literal notranslate"><span class="pre">None</span></code>, the elements are compared directly and | |
| no key function is called.</p> | |
| <div class="versionchanged"> | |
| <p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p> | |
| </div> | |
| </dd></dl> | |
| <dl class="py function"> | |
| <dt class="sig sig-object py" id="bisect.bisect_right"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect_right</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.bisect_right" title="Link to this definition">¶</a></dt> | |
| <dt class="sig sig-object py" id="bisect.bisect"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">bisect</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.bisect" title="Link to this definition">¶</a></dt> | |
| <dd><p>Similar to <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_left()</span></code></a>, but returns an insertion point which comes | |
| after (to the right of) any existing entries of <em>x</em> in <em>a</em>.</p> | |
| <p>The returned insertion point <em>ip</em> partitions the array <em>a</em> into two slices | |
| such that <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre"><=</span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[lo</span> <span class="pre">:</span> <span class="pre">ip])</span></code> is true for the left slice and | |
| <code class="docutils literal notranslate"><span class="pre">all(elem</span> <span class="pre">></span> <span class="pre">x</span> <span class="pre">for</span> <span class="pre">elem</span> <span class="pre">in</span> <span class="pre">a[ip</span> <span class="pre">:</span> <span class="pre">hi])</span></code> is true for the right slice.</p> | |
| <div class="versionchanged"> | |
| <p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p> | |
| </div> | |
| </dd></dl> | |
| <dl class="py function"> | |
| <dt class="sig sig-object py" id="bisect.insort_left"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort_left</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.insort_left" title="Link to this definition">¶</a></dt> | |
| <dd><p>Insert <em>x</em> in <em>a</em> in sorted order.</p> | |
| <p>This function first runs <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_left()</span></code></a> to locate an insertion point. | |
| Next, it runs the <a class="reference internal" href="stdtypes.html#sequence.insert" title="sequence.insert"><code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code></a> method on <em>a</em> to insert <em>x</em> at the | |
| appropriate position to maintain sort order.</p> | |
| <p>To support inserting records in a table, the <em>key</em> function (if any) is | |
| applied to <em>x</em> for the search step but not for the insertion step.</p> | |
| <p>Keep in mind that the <em>O</em>(log <em>n</em>) search is dominated by the slow <em>O</em>(<em>n</em>) | |
| insertion step.</p> | |
| <div class="versionchanged"> | |
| <p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p> | |
| </div> | |
| </dd></dl> | |
| <dl class="py function"> | |
| <dt class="sig sig-object py" id="bisect.insort_right"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort_right</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.insort_right" title="Link to this definition">¶</a></dt> | |
| <dt class="sig sig-object py" id="bisect.insort"> | |
| <span class="sig-prename descclassname"><span class="pre">bisect.</span></span><span class="sig-name descname"><span class="pre">insort</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">x</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lo</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">hi</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">len(a)</span></span></em>, <em class="sig-param"><span class="keyword-only-separator o"><abbr title="Keyword-only parameters separator (PEP 3102)"><span class="pre">*</span></abbr></span></em>, <em class="sig-param"><span class="n"><span class="pre">key</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bisect.insort" title="Link to this definition">¶</a></dt> | |
| <dd><p>Similar to <a class="reference internal" href="#bisect.insort_left" title="bisect.insort_left"><code class="xref py py-func docutils literal notranslate"><span class="pre">insort_left()</span></code></a>, but inserting <em>x</em> in <em>a</em> after any existing | |
| entries of <em>x</em>.</p> | |
| <p>This function first runs <a class="reference internal" href="#bisect.bisect_right" title="bisect.bisect_right"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect_right()</span></code></a> to locate an insertion point. | |
| Next, it runs the <a class="reference internal" href="stdtypes.html#sequence.insert" title="sequence.insert"><code class="xref py py-meth docutils literal notranslate"><span class="pre">insert()</span></code></a> method on <em>a</em> to insert <em>x</em> at the | |
| appropriate position to maintain sort order.</p> | |
| <p>To support inserting records in a table, the <em>key</em> function (if any) is | |
| applied to <em>x</em> for the search step but not for the insertion step.</p> | |
| <p>Keep in mind that the <em>O</em>(log <em>n</em>) search is dominated by the slow <em>O</em>(<em>n</em>) | |
| insertion step.</p> | |
| <div class="versionchanged"> | |
| <p><span class="versionmodified changed">Changed in version 3.10: </span>Added the <em>key</em> parameter.</p> | |
| </div> | |
| </dd></dl> | |
| <section id="performance-notes"> | |
| <h2>Performance Notes<a class="headerlink" href="#performance-notes" title="Link to this heading">¶</a></h2> | |
| <p>When writing time sensitive code using <em>bisect()</em> and <em>insort()</em>, keep these | |
| thoughts in mind:</p> | |
| <ul class="simple"> | |
| <li><p>Bisection is effective for searching ranges of values. | |
| For locating specific values, dictionaries are more performant.</p></li> | |
| <li><p>The <em>insort()</em> functions are <em>O</em>(<em>n</em>) because the logarithmic search step | |
| is dominated by the linear time insertion step.</p></li> | |
| <li><p>The search functions are stateless and discard key function results after | |
| they are used. Consequently, if the search functions are used in a loop, | |
| the key function may be called again and again on the same array elements. | |
| If the key function isn’t fast, consider wrapping it with | |
| <a class="reference internal" href="functools.html#functools.cache" title="functools.cache"><code class="xref py py-func docutils literal notranslate"><span class="pre">functools.cache()</span></code></a> to avoid duplicate computations. Alternatively, | |
| consider searching an array of precomputed keys to locate the insertion | |
| point (as shown in the examples section below).</p></li> | |
| </ul> | |
| <div class="admonition seealso"> | |
| <p class="admonition-title">See also</p> | |
| <ul class="simple"> | |
| <li><p><a class="reference external" href="https://grantjenks.com/docs/sortedcollections/">Sorted Collections</a> is a high performance | |
| module that uses <em>bisect</em> to managed sorted collections of data.</p></li> | |
| <li><p>The <a class="reference external" href="https://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> uses | |
| bisect to build a full-featured collection class with straight-forward search | |
| methods and support for a key-function. The keys are precomputed to save | |
| unnecessary calls to the key function during searches.</p></li> | |
| </ul> | |
| </div> | |
| </section> | |
| <section id="searching-sorted-lists"> | |
| <h2>Searching Sorted Lists<a class="headerlink" href="#searching-sorted-lists" title="Link to this heading">¶</a></h2> | |
| <p>The above <a class="reference internal" href="#bisect-functions">bisect functions</a> are useful for finding insertion points but | |
| can be tricky or awkward to use for common searching tasks. The following five | |
| functions show how to transform them into the standard lookups for sorted | |
| lists:</p> | |
| <div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span><span class="w"> </span><span class="nf">index</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> | |
| <span class="s1">'Locate the leftmost value exactly equal to x'</span> | |
| <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> | |
| <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="ow">and</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">:</span> | |
| <span class="k">return</span> <span class="n">i</span> | |
| <span class="k">raise</span> <span class="ne">ValueError</span> | |
| <span class="k">def</span><span class="w"> </span><span class="nf">find_lt</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> | |
| <span class="s1">'Find rightmost value less than x'</span> | |
| <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> | |
| <span class="k">if</span> <span class="n">i</span><span class="p">:</span> | |
| <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> | |
| <span class="k">raise</span> <span class="ne">ValueError</span> | |
| <span class="k">def</span><span class="w"> </span><span class="nf">find_le</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> | |
| <span class="s1">'Find rightmost value less than or equal to x'</span> | |
| <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_right</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> | |
| <span class="k">if</span> <span class="n">i</span><span class="p">:</span> | |
| <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> | |
| <span class="k">raise</span> <span class="ne">ValueError</span> | |
| <span class="k">def</span><span class="w"> </span><span class="nf">find_gt</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> | |
| <span class="s1">'Find leftmost value greater than x'</span> | |
| <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_right</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> | |
| <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">):</span> | |
| <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> | |
| <span class="k">raise</span> <span class="ne">ValueError</span> | |
| <span class="k">def</span><span class="w"> </span><span class="nf">find_ge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span> | |
| <span class="s1">'Find leftmost item greater than or equal to x'</span> | |
| <span class="n">i</span> <span class="o">=</span> <span class="n">bisect_left</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> | |
| <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">):</span> | |
| <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> | |
| <span class="k">raise</span> <span class="ne">ValueError</span> | |
| </pre></div> | |
| </div> | |
| </section> | |
| <section id="examples"> | |
| <h2>Examples<a class="headerlink" href="#examples" title="Link to this heading">¶</a></h2> | |
| <p id="bisect-example">The <a class="reference internal" href="#bisect.bisect" title="bisect.bisect"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></a> function can be useful for numeric table lookups. This | |
| example uses <code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code> to look up a letter grade for an exam score (say) | |
| based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is | |
| a ‘B’, and so on:</p> | |
| <div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="k">def</span><span class="w"> </span><span class="nf">grade</span><span class="p">(</span><span class="n">score</span><span class="p">)</span> | |
| <span class="gp">... </span> <span class="n">i</span> <span class="o">=</span> <span class="n">bisect</span><span class="p">([</span><span class="mi">60</span><span class="p">,</span> <span class="mi">70</span><span class="p">,</span> <span class="mi">80</span><span class="p">,</span> <span class="mi">90</span><span class="p">],</span> <span class="n">score</span><span class="p">)</span> | |
| <span class="gp">... </span> <span class="k">return</span> <span class="s2">"FDCBA"</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> | |
| <span class="gp">...</span> | |
| <span class="gp">>>> </span><span class="p">[</span><span class="n">grade</span><span class="p">(</span><span class="n">score</span><span class="p">)</span> <span class="k">for</span> <span class="n">score</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">33</span><span class="p">,</span> <span class="mi">99</span><span class="p">,</span> <span class="mi">77</span><span class="p">,</span> <span class="mi">70</span><span class="p">,</span> <span class="mi">89</span><span class="p">,</span> <span class="mi">90</span><span class="p">,</span> <span class="mi">100</span><span class="p">]]</span> | |
| <span class="go">['F', 'A', 'C', 'C', 'B', 'A', 'A']</span> | |
| </pre></div> | |
| </div> | |
| <p>The <a class="reference internal" href="#bisect.bisect" title="bisect.bisect"><code class="xref py py-func docutils literal notranslate"><span class="pre">bisect()</span></code></a> and <a class="reference internal" href="#bisect.insort" title="bisect.insort"><code class="xref py py-func docutils literal notranslate"><span class="pre">insort()</span></code></a> functions also work with | |
| lists of tuples. The <em>key</em> argument can serve to extract the field used for ordering | |
| records in a table:</p> | |
| <div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="kn">from</span><span class="w"> </span><span class="nn">collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">namedtuple</span> | |
| <span class="gp">>>> </span><span class="kn">from</span><span class="w"> </span><span class="nn">operator</span><span class="w"> </span><span class="kn">import</span> <span class="n">attrgetter</span> | |
| <span class="gp">>>> </span><span class="kn">from</span><span class="w"> </span><span class="nn">bisect</span><span class="w"> </span><span class="kn">import</span> <span class="n">bisect</span><span class="p">,</span> <span class="n">insort</span> | |
| <span class="gp">>>> </span><span class="kn">from</span><span class="w"> </span><span class="nn">pprint</span><span class="w"> </span><span class="kn">import</span> <span class="n">pprint</span> | |
| <span class="gp">>>> </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> | |
| <span class="gp">>>> </span><span class="n">movies</span> <span class="o">=</span> <span class="p">[</span> | |
| <span class="gp">... </span> <span class="n">Movie</span><span class="p">(</span><span class="s1">'Jaws'</span><span class="p">,</span> <span class="mi">1975</span><span class="p">,</span> <span class="s1">'Spielberg'</span><span class="p">),</span> | |
| <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> | |
| <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> | |
| <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> | |
| <span class="gp">... </span><span class="p">]</span> | |
| <span class="gp">>>> </span><span class="c1"># Find the first movie released after 1960</span> | |
| <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> | |
| <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> | |
| <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> | |
| <span class="go">Movie(name='The Birds', released=1963, director='Hitchcock')</span> | |
| <span class="gp">>>> </span><span class="c1"># Insert a movie while maintaining sort order</span> | |
| <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> | |
| <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> | |
| <span class="gp">>>> </span><span class="n">pprint</span><span class="p">(</span><span class="n">movies</span><span class="p">)</span> | |
| <span class="go">[Movie(name='The Birds', released=1963, director='Hitchcock'),</span> | |
| <span class="go"> Movie(name='Love Story', released=1970, director='Hiller'),</span> | |
| <span class="go"> Movie(name='Jaws', released=1975, director='Spielberg'),</span> | |
| <span class="go"> Movie(name='Aliens', released=1986, director='Cameron'),</span> | |
| <span class="go"> Movie(name='Titanic', released=1997, director='Cameron')]</span> | |
| </pre></div> | |
| </div> | |
| <p>If the key function is expensive, it is possible to avoid repeated function | |
| calls by searching a list of precomputed keys to find the index of a record:</p> | |
| <div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </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> | |
| <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> | |
| <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> | |
| <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span> | |
| <span class="go">('black', 0)</span> | |
| <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">1</span><span class="p">)]</span> | |
| <span class="go">('blue', 1)</span> | |
| <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">5</span><span class="p">)]</span> | |
| <span class="go">('red', 5)</span> | |
| <span class="gp">>>> </span><span class="n">data</span><span class="p">[</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">keys</span><span class="p">,</span> <span class="mi">8</span><span class="p">)]</span> | |
| <span class="go">('yellow', 8)</span> | |
| </pre></div> | |
| </div> | |
| </section> | |
| </section> | |
| <div class="clearer"></div> | |
| </div> | |
| </div> | |
| </div> | |
| <div class="sphinxsidebar" role="navigation" aria-label="Main"> | |
| <div class="sphinxsidebarwrapper"> | |
| <div> | |
| <h3><a href="../contents.html">Table of Contents</a></h3> | |
| <ul> | |
| <li><a class="reference internal" href="#"><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a><ul> | |
| <li><a class="reference internal" href="#performance-notes">Performance Notes</a></li> | |
| <li><a class="reference internal" href="#searching-sorted-lists">Searching Sorted Lists</a></li> | |
| <li><a class="reference internal" href="#examples">Examples</a></li> | |
| </ul> | |
| </li> | |
| </ul> | |
| </div> | |
| <div> | |
| <h4>Previous topic</h4> | |
| <p class="topless"><a href="heapq.html" | |
| title="previous chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a></p> | |
| </div> | |
| <div> | |
| <h4>Next topic</h4> | |
| <p class="topless"><a href="array.html" | |
| title="next chapter"><code class="xref py py-mod docutils literal notranslate"><span class="pre">array</span></code> — Efficient arrays of numeric values</a></p> | |
| </div> | |
| <script> | |
| document.addEventListener('DOMContentLoaded', () => { | |
| const title = document.querySelector('meta[property="og:title"]').content; | |
| const elements = document.querySelectorAll('.improvepage'); | |
| const pageurl = window.location.href.split('?')[0]; | |
| elements.forEach(element => { | |
| const url = new URL(element.href.split('?')[0].replace("-nojs", "")); | |
| url.searchParams.set('pagetitle', title); | |
| url.searchParams.set('pageurl', pageurl); | |
| url.searchParams.set('pagesource', "library/bisect.rst"); | |
| element.href = url.toString(); | |
| }); | |
| }); | |
| </script> | |
| <div role="note" aria-label="source link"> | |
| <h3>This page</h3> | |
| <ul class="this-page-menu"> | |
| <li><a href="../bugs.html">Report a bug</a></li> | |
| <li><a class="improvepage" href="../improve-page-nojs.html">Improve this page</a></li> | |
| <li> | |
| <a href="https://github.com/python/cpython/blob/main/Doc/library/bisect.rst?plain=1" | |
| rel="nofollow">Show source | |
| </a> | |
| </li> | |
| </ul> | |
| </div> | |
| </div> | |
| <div id="sidebarbutton" title="Collapse sidebar"> | |
| <span>«</span> | |
| </div> | |
| </div> | |
| <div class="clearer"></div> | |
| </div> | |
| <div class="related" role="navigation" aria-label="Related"> | |
| <h3>Navigation</h3> | |
| <ul> | |
| <li class="right" style="margin-right: 10px"> | |
| <a href="../genindex.html" title="General Index" | |
| >index</a></li> | |
| <li class="right" > | |
| <a href="../py-modindex.html" title="Python Module Index" | |
| >modules</a> |</li> | |
| <li class="right" > | |
| <a href="array.html" title="array — Efficient arrays of numeric values" | |
| >next</a> |</li> | |
| <li class="right" > | |
| <a href="heapq.html" title="heapq — Heap queue algorithm" | |
| >previous</a> |</li> | |
| <li><img src="../_static/py.svg" alt="Python logo" style="vertical-align: middle; margin-top: -1px"></li> | |
| <li><a href="https://www.python.org/">Python</a> »</li> | |
| <li class="switchers"> | |
| <div class="language_switcher_placeholder"></div> | |
| <div class="version_switcher_placeholder"></div> | |
| </li> | |
| <li> | |
| </li> | |
| <li id="cpython-language-and-version"> | |
| <a href="../index.html">3.15.0a6 Documentation</a> » | |
| </li> | |
| <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li> | |
| <li class="nav-item nav-item-2"><a href="datatypes.html" >Data Types</a> »</li> | |
| <li class="nav-item nav-item-this"><a href=""><code class="xref py py-mod docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a></li> | |
| <li class="right"> | |
| <div class="inline-search" role="search"> | |
| <form class="inline-search" action="../search.html" method="get"> | |
| <input placeholder="Quick search" aria-label="Quick search" type="search" name="q" id="search-box"> | |
| <input type="submit" value="Go"> | |
| </form> | |
| </div> | |
| | | |
| </li> | |
| <li class="right"> | |
| <label class="theme-selector-label"> | |
| Theme | |
| <select class="theme-selector" oninput="activateTheme(this.value)"> | |
| <option value="auto" selected>Auto</option> | |
| <option value="light">Light</option> | |
| <option value="dark">Dark</option> | |
| </select> | |
| </label> |</li> | |
| </ul> | |
| </div> | |
| <div class="footer"> | |
| © <a href="../copyright.html">Copyright</a> 2001 Python Software Foundation. | |
| <br> | |
| This page is licensed under the Python Software Foundation License Version 2. | |
| <br> | |
| Examples, recipes, and other code in the documentation are additionally licensed under the Zero Clause BSD License. | |
| <br> | |
| See <a href="/license.html">History and License</a> for more information.<br> | |
| <br> | |
| The Python Software Foundation is a non-profit corporation. | |
| <a href="https://www.python.org/psf/donations/">Please donate.</a> | |
| <br> | |
| <br> | |
| Last updated on Mar 10, 2026 (08:58 UTC). | |
| <a href="/bugs.html">Found a bug</a>? | |
| <br> | |
| Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 8.2.3. | |
| </div> | |
| </body> | |
| </html> |