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.
