Skip to main content

Browse the archive

Staging
v0.5.1
https://github.com/python/cpython
09 December 2020, 11:06:31 UTC
Revision 2a9b0a93091b9ef7350a94bb3d3f1c43725b7a8c authored by Georg Brandl on 05 March 2011, 13:54:19 UTC, committed by Georg Brandl on 05 March 2011, 13:54:19 UTC 
Close 2.0 branch.
1 parent a741ab6
Raw File
Tip revision: 2a9b0a93091b9ef7350a94bb3d3f1c43725b7a8c authored by Georg Brandl on 05 March 2011, 13:54:19 UTC
Close 2.0 branch.
Tip revision: 2a9b0a9
bisect.py 
"""Bisection algorithms."""


def insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted."""
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)/2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)


def bisect(a, x, lo=0, hi=None):
    """Find the index where to insert item x in list a, assuming a is sorted."""
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)/2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo
back to top