endless automata

After reading Are you one of the 10% of programmers who can write a binary search?, I decided to find out if I was. Here’s my submission (written in about 30 minutes in python):

# the list to be searched
data = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

# what we're searching for
search = 7

# we could do this recursively, but without tail
# call optimization we'd just reach a stack overflow
# shortly - lame - so we'll go iterative
found = False
while not found:
    # did we run out of data?
    if len(data) == 0: break

    # partition the list (take advantage of default
    # integer division in 2.6)
    p = len(data) / 2

    # proceed based on data at partition
    if data[p] == search:
        found = True
        break
    elif data[p] > search:
        data = data[:p]
    else:
        data = data[p+1:]

if found:
    print "Found it!"
else:
    print "Not found."

I had a bit of an easier time thanks to python’s arbitrary length integers, and list splicing notation. This algorithm would have been a lot more error prone in C/Java style language.

Thursday March 18th at 7:30 I’ll be playing transition pieces for a science themed poetry reading at the Creole Gallery in Old Town. I’ll be doing my best to add a nice old school Sci-Fi vibe. $3 donation. Open Mic readings after the show ends. Hope to see you there!