Home//

Python Binary Search Implementation: Iterative and Recursive

# Python Binary Search Implementation: Iterative and Recursive 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 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. 