Ye Olde Binary Search

[Warren Postma]

Is there a builtin somewhere in Python to do a binary search on a list?


1. Recursion is restricted to a depth of len(list)/2 or less. This slows
down the algorithm, but it's safer.  Deep recursion problems currently cause
Python 1.5.2 on
Windows to Bomb Out unless you recompile with a smaller maximum recursion
depth.

2. Is there faster way to check if a list is sorted than just always calling
list.sort()?

3. Has anyone written a faster/better one of these in native C?

4. Has anyone ever considered an "inorder_insert" and a "search" method be
added to the built-in Python list type, making it a auto-sorted-array with
fast searching, if we so desired?  If there is a good solution to #2, would
it be possible for search to note quickly that a list is in sorted order,
and therefore use the faster binary search, otherwise it would use a slower
iterative search (The Bad Old Way).

Warren

---

import exceptions

def _bin_search(list,item,first=0,last=-1,depth=0):
    "return index of 'item' in 'list'. assumes list is sorted"
    if (depth>len(list)/2):
        raise StandardError, "_bin_search internal failure"
    if last < 0:
        last = len(list)-1
    x=last-first
    if (x<0):
        return -1
    if (x==0):
        n = first
    else:
        n = first + (x+1)/2
    #print "item=",item, "list[",n,"]=",list[n],"first=",first,"last=",last
    # binary search: split, recurse subrange:
    if list[n] == item:
        return n
    elif item < list[n]:
        #print "<"
        return _bin_search(list,item,first,n-1,depth+1)
    else:
        #print ">"
        return _bin_search(list,item,n+1,last,depth+1)


# test code:
if __name__ == '__main__':
     print _bin_search( [0,5,928,10982,1089280,129839803,1231209833],
129839803 )
    n = range(0,32134,81)
    x = _bin_search(  n, 21303 )
    print n[x],x