Home//

Python Binary Search Implementation: Iterative and Recursive

Python Binary Search Implementation: Iterative and Recursive

Minh Vu

By Minh Vu

Updated Nov 30, 2023

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!

How Binary Search Works

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:

  1. Compare the target element with the middle element.
  2. If the target element is equal to the middle element, we can return the index of the middle element.
  3. 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.
  4. 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:

Binary Search Visualization, Source: DevOpedia
Figure: Binary Search Visualization, Source: DevOpedia

Binary Search Implementation in Python

Now, let's implement the Binary Search algorithm in Python in 2 ways: iterative and recursive.

Iterative Binary Search in Python

binary-search.py
def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 # pick the middle element if arr[mid] == target: # if the middle element is the target, return its index return mid elif arr[mid] < target: # if the middle element is less than the target, ignore the left half left = mid + 1 else: # if the middle element is greater than the target, ignore the right half right = mid - 1 return -1 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] print(binary_search(arr, 5)) # Output: 4 print(binary_search(arr, 100)) # Output: -1

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.

Recursive Binary Search in Python

binary-search.py
def binary_search(arr, target, left, right): if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, right) else: return binary_search(arr, target, left, mid - 1) arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] print(binary_search(arr, 5, 0, len(arr) - 1)) # Output: 4 print(binary_search(arr, 100, 0, len(arr) - 1)) # Output: -1

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).

Conclusion

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.

You can search for other posts at home page.
Minh Vu

Minh Vu

Software Engineer

Hi guys, I'm the author of WiseCode Blog. I mainly work with the Elastic Stack and build AI & Python projects. I also love writing technical articles, hope you guys have good experience reading my blog!