19 March

Our array-search program, from class.

import random
N = 1000
xs = [int(random.random()*N) for i in xrange(N)]
xs.sort()
print xs

goal = int(raw_input("Enter number to find: "))
print "You seek", goal

# Linear search
print "*** Linear search"
for i in xrange(len(xs)):
    if xs[i] == goal:
        print "Found at position", i

# Binary search
print "*** Binary search"
i = 0
j = len(xs)
while i < j:
    mid = (i+j)/2
    print i, mid, j
    if xs[mid] == goal:
        print "Found at position", mid
        j = i
    if xs[mid] < goal:  # go right
        print "go right"
        i = mid+1
    if xs[mid] > goal:  # go left
        print "go left"
        j = mid