Binary Search
Aug 26 2019
Binary Search comes up quite a lot when the topic of time complexity arises, particularly during coding interview-type questions. So, I figured it would be worthwhile to wrap my head around this. Binary search can find a target value from a sorted array (data has to be sorted) at log n time, compared to just iterating through the whole list using a loop, which would be linear time or n.
There is a lot of information on binary search out there, but it still took me a little while to wrap my head around it because of the way most of the functions were written. I would say it pays to just write your own function once you understand the basic principles. Below is my iterative binary search function. It's a little wordy but it clearly describes what's going on.
def iterative_binary_search(target, array):
start = 0
end = len(array) - 1
if target > array[len(array) - 1]:
print("Error: target greater than array.")
return False
if target < array[0]:
print("Error: target less than array.")
return False
while start <= end:
halfway = (start + end) // 2
if target == array[halfway]:
print(f"position of target in array is={halfway}")
return True
elif target < array[halfway]:
end = halfway - 1
print(f"halfway={array[halfway]} was greater than {target} so now end={end}")
else:
start = halfway + 1
print(f"halfway={array[halfway]} was less than {target} so now start={start}")
print("Error: target not found within array.")
return False