Back to index

python3.2  3.2.2
Functions | Variables
bisect Namespace Reference

Functions

def insort_right
def bisect_right
def insort_left
def bisect_left

Variables

 insort = insort_right
 bisect = bisect_right

Detailed Description

Bisection algorithms.

Function Documentation

def bisect.bisect_left (   a,
  x,
  lo = 0,
  hi = None 
)
Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.

Definition at line 67 of file bisect.py.

00067 
00068 def bisect_left(a, x, lo=0, hi=None):
00069     """Return the index where to insert item x in list a, assuming a is sorted.
00070 
00071     The return value i is such that all e in a[:i] have e < x, and all e in
00072     a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
00073     insert just before the leftmost x already there.
00074 
00075     Optional args lo (default 0) and hi (default len(a)) bound the
00076     slice of a to be searched.
00077     """
00078 
00079     if lo < 0:
00080         raise ValueError('lo must be non-negative')
00081     if hi is None:
00082         hi = len(a)
00083     while lo < hi:
00084         mid = (lo+hi)//2
00085         if a[mid] < x: lo = mid+1
00086         else: hi = mid
00087     return lo
00088 
00089 # Overwrite above definitions with a fast C implementation
00090 try:
    from _bisect import *

Here is the caller graph for this function:

def bisect.bisect_right (   a,
  x,
  lo = 0,
  hi = None 
)
Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.

Definition at line 24 of file bisect.py.

00024 
00025 def bisect_right(a, x, lo=0, hi=None):
00026     """Return the index where to insert item x in list a, assuming a is sorted.
00027 
00028     The return value i is such that all e in a[:i] have e <= x, and all e in
00029     a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
00030     insert just after the rightmost x already there.
00031 
00032     Optional args lo (default 0) and hi (default len(a)) bound the
00033     slice of a to be searched.
00034     """
00035 
00036     if lo < 0:
00037         raise ValueError('lo must be non-negative')
00038     if hi is None:
00039         hi = len(a)
00040     while lo < hi:
00041         mid = (lo+hi)//2
00042         if x < a[mid]: hi = mid
00043         else: lo = mid+1
00044     return lo

def bisect.insort_left (   a,
  x,
  lo = 0,
  hi = None 
)
Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the left of the leftmost x.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.

Definition at line 47 of file bisect.py.

00047 
00048 def insort_left(a, x, lo=0, hi=None):
00049     """Insert item x in list a, and keep it sorted assuming a is sorted.
00050 
00051     If x is already in a, insert it to the left of the leftmost x.
00052 
00053     Optional args lo (default 0) and hi (default len(a)) bound the
00054     slice of a to be searched.
00055     """
00056 
00057     if lo < 0:
00058         raise ValueError('lo must be non-negative')
00059     if hi is None:
00060         hi = len(a)
00061     while lo < hi:
00062         mid = (lo+hi)//2
00063         if a[mid] < x: lo = mid+1
00064         else: hi = mid
00065     a.insert(lo, x)
00066 

def bisect.insort_right (   a,
  x,
  lo = 0,
  hi = None 
)
Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the right of the rightmost x.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.

Definition at line 3 of file bisect.py.

00003 
00004 def insort_right(a, x, lo=0, hi=None):
00005     """Insert item x in list a, and keep it sorted assuming a is sorted.
00006 
00007     If x is already in a, insert it to the right of the rightmost x.
00008 
00009     Optional args lo (default 0) and hi (default len(a)) bound the
00010     slice of a to be searched.
00011     """
00012 
00013     if lo < 0:
00014         raise ValueError('lo must be non-negative')
00015     if hi is None:
00016         hi = len(a)
00017     while lo < hi:
00018         mid = (lo+hi)//2
00019         if x < a[mid]: hi = mid
00020         else: lo = mid+1
00021     a.insert(lo, x)


Variable Documentation

Definition at line 45 of file bisect.py.

Definition at line 22 of file bisect.py.