Iterative binary search in Python

This post is a rewrite of the following article but in Python

Iterative binary search

Python code

def IterativeBinarySearch(A, key, l, r): 
	# As long as left index is less than right index
	while l <= r: 
		# Middle element
		m = (l + r)/2
		
		# If the search key on the left half
		if key < A[m]:
			# Update right index
			r = m - 1
		
		# If the search key on the right half
		elif key > A[m]:
			# Update the left index
			l = m + 1
		
		# We found the key
		else:
			return m
	
	# Key was not found
	return -1

#    0, 1, 2, 3,  4,  5,  6,  7,  8,   9
A = [1, 2, 3, 17, 25, 44, 67, 99, 203, 500]

# Search for numbers between 1 and 500
# Only print numbers that exists
for i in range(0, 501):
	r = IterativeBinarySearch(A, i, 0, len(A)-1)
	if r != -1:
		print  "Position of {} in array is {}".format(i, r)

If you run the code snippet above, you should get the following output

Position of 1 in array is 0
Position of 2 in array is 1
Position of 3 in array is 2
Position of 17 in array is 3
Position of 25 in array is 4
Position of 44 in array is 5
Position of 67 in array is 6
Position of 99 in array is 7
Position of 203 in array is 8
Position of 500 in array is 9

Please leave a comment if you have questions or corrections. Thanks

Leave a Reply