Lectures‎ > ‎

Week14

Computational Complexity

O(1), O(n), O(log n), O(n^2)

Binary Search

Binary search is a technique speedup search for an element in a sequence if we know the sequence elements are sorted.

Here is the implementation of binary search we developed in class:

L = [0,1,2,3,5,6,7,8,9,10,11,13,14,15,16,17]

def binary_search(x, L):
    if L == []:
        return False
    elif len(L) == 1:
        return x == L[0]
    else:
        midindex = len(L) / 2
        midvalue = L[midindex]
        if x == midvalue:
            return True
        elif x < midvalue:
            return binary_search(x, L[0:midindex])
        elif x > midvalue:
            return binary_search(x, L[midindex:])

print binary_search(14, L)
print binary_search(4, L)

Binary search: finding the index

L = [0,1,2,3,5,6,7,8,9,10,11,13,14,15,16,17]

def binary_search_helper(x, L, index):
    '''
    Binary search helper for finding the index of x in L.
    
    If x is not in L, then return -1
    
    This works by keeping track of the current index offset on each
    recursive call.
    '''
    
    if L == []:
        return -1
    elif len(L) == 1:
        if x == L[0]:
            return index
        else:
            return -1
    else:
        midindex = len(L) / 2
        midvalue = L[midindex]
        if x == midvalue:
            return index + midindex
        elif x < midvalue:
            return binary_search_helper(x, L[0:midindex], index)
        elif x > midvalue:
            return binary_search_helper(x, L[midindex:], index + midindex)

def binary_search_index(x, L):
    return binary_search_helper(x, L, 0)

print binary_search_index(14, L)
print binary_search_index(4, L)


Object Oriented Programming

Classes, Instances/Objects, Initialization, Attributes, Methods

Deck of cards example


Comments