November 11, 2017
Iterative binary search in Python
This post is a rewrite of the following article but in Python
Python code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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
|
1 2 3 4 5 6 7 8 9 10 |
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
About Author
Mohammed Abualrob
Software Engineer @ Cisco