Understand binary serach
The whole idea behind binary search is that you can take advantage of having the list you search in ordered.
Say, we need to search for 7 and we look at the element in the middle of the list.
Then we can conclude, in this example, that 7 is not part of the right side of the list, as all numbers must be greater than 10. That is because the list is ordered.
Next we ask the in the middle of the left side of the list which is left unknown is 7 is there.
As -9 is less than 7, we know that 7 cannot be before in the list and are left with the remaining element between -9 and 10.
As -3 is less than 7, we know that if 7 is part of the list, then it must be to the right of -3. Also, we know it must be before 10 (our first comparison).
Hence, it can only be in the last spot left. But as it is 8, we now know that 7 is not part of the list.
Why is that impressive?
Consider if the list was unsorted. Then you would have to look through the entire list to make sure 7 was not part of it.
In terms of complexity that means if the list contains N element, it must make N comparisons to search of an element. That is O(N) time complexity.
The binary search on the other hand is way more efficient. For each comparison the algorithm can skip one half of the list. That is O(log(N)) time complexity.
The source code
def recursive_binary_search(my_list, element):
return recursive_binary_search_internal(my_list, element, 0, len(my_list) - 1)
def recursive_binary_search_internal(my_list, element, low, high):
if low > high:
return False
else:
mid = (low + high)//2
if my_list[mid] == element:
return True
else:
if my_list[mid] > element:
return recursive_binary_search_internal(my_list, element, low, mid - 1)
else:
return recursive_binary_search_internal(my_list, element, mid + 1, high)
def binary_search(my_list, element):
low = 0
high = len(my_list) - 1
while low <= high:
mid = (low + high)//2
if my_list[mid] == element:
return True
else:
if my_list[mid] > element:
high = mid - 1
else:
low = mid + 1
return False
def main():
my_list = [-29, -16, -15, -9, -6, -3, 8, 10, 17, 19, 27, 47, 54, 56, 60]
print(my_list)
element = 56
print("Binary Search:", binary_search(my_list, element), element)
print("Recursive Binary Search:", recursive_binary_search(my_list, element), element)
if __name__ == "__main__":
main()
There are two implementations of the binary search in the above example.
Want to learn how to sort a list?
For the insertion sort read this tutorial. For the merge sort read this tutorial.