Linear and Binary Search

The example algorithm we use to solve the guessing game.

Linear Search

def search(xs, target):
	for i in range(len(xs)):
		if xs[i] == target:
			return i
	return -1

xs= [1,2,3,4,5,6,7]
location = search(xs, 5)
if location != -1:
	print("The location of the item is: {}".format(location))
else:
	print("The item was not found")

Q What are the steps (in English) this code is performing?

Q What is the ‘best’ case (ie the one which requires the fewest steps)?

Q What is the ‘worst’ case (ie, the one which requires the most steps)?

(Extention) This code is not very ‘pythonic’ - how could the code be rewritten to be more pythonic?

Binary Search

def search(xs, target):
	# TODO

xs= [1,2,3,4,5,6,7]
location = search(xs, 5)
if location != -1:
	print("The location of the item is: {}".format(location))
else:
	print("The item was not found")

Q What are the steps (in English) this code is performing?

Q What is the ‘best’ case (ie the one which requires the fewest steps)?

Q What is the ‘worst’ case (ie, the one which requires the most steps)?

Q What situations would the ‘Linear’ version work and the ‘Binary’ version not work (what assumption is being made)?

Last updated 0001-01-01