Binary Search is an efficient algorithm to search for an element in a sorted list with O(log n) time complexity.
In this tutorial, I will show you how to write a Python program to implement Binary Search using 2 ways: iterative and recursive. Let's get started!
Table of Contents
Before going to the implementation, you should understand the mechanism behind Binary Search to see why it's faster than Linear Search.
In short, the Binary Search algorithm can be applied to a sorted list by dividing the list into two halves and ignore the half that doesn't contain the target element.
Assuming that we have a target element (the number we need to find), a middle element, and a list sorted ascendingly:
- Compare the target element with the middle element.
- If the target element is equal to the middle element, we can return the index of the middle element.
- If the target element is greater than the middle element, we can ignore the left half of the list and continue the search on the right half.
- If the target element is less than the middle element, we can ignore the right half of the list and continue the search on the left half.
See the visualization of the Binary Search algorithm below:
Now, let's implement the Binary Search algorithm in Python in 2 ways: iterative and recursive.
I recommend using this approach as the space complexity is O(1) and it's easier to understand than the recursive approach. But if you want to learn how to implement the recursive approach, keep reading.
The recursive approach is more expensive as it has to create Call Stack for each recursive call. So the space complexity is O(log n).
In this tutorial, we have learned how to implement Binary Search in Python using 2 ways:
- Iterative Binary Search: using a while loop.
- Recursive Binary Search: using a recursive function.
If you are still confused about the Binary Search algorithm, comment below so I will try to help you.