Some Algorithms In Python

some_algorithms.py

# binary search
def binary_search(x, arr):
    """
    x is a integer,
    arr is an array of integers, in sorted order
    
    Binary search will tell you if x is contained in arr
    
    A binary search bisects the array, recursively, to search smaller and smaller 
        sub-sections of the array until it either, finds the value or finds no more candidate
        values between two values in the array that are directly greater than and less than
        the value being searched for.
    """
    if len(arr) == 0:
        print "empty, not found"
        out = false # not in empty array
    elif len(arr) == 1:
        print "one entry"
        out = x == arr[0] # it's either == the only entry or it isn't
    else:
        midIdx = len(arr) / 2 # get the middle index of the array, round down
        middleValue = arr[midIdx]
        print "splitting on %d..." % middleValue
        if x == middleValue:
            out = True # if it's equal to it, we're done
        elif x < middleValue:
            out = binary_search(x, arr[:midIdx]) # binary search left, less than side
        else:
            out = binary_search(x, arr[midIdx:]) # binary seach right, greater than side
    return out

# run binary search
def run_binary_search():
  print "searching for '6' in the integers 0 through 99"
  binary_search(6, range(100))