Binary Search in Python – How to Code the Algorithm with Examples

As programmers, we frequently need to search for specific data within large datasets. Writing efficient search algorithms is crucial for good performance, especially as the amount of data grows very large.

One of the most effective search algorithms is binary search. In this post, we‘ll take an in-depth look at what binary search is, how it works, and how to implement it in Python. We‘ll walk through detailed examples to help illustrate the concepts.

What is Binary Search?

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you‘ve narrowed down the possible locations to just one.

We can think of binary search as a "divide and conquer" approach. Here‘s the basic idea:

1. Let min = 1 and max = n (n is the number of elements in the array).
2. Compare x (the number we‘re searching for) to the middle element of the array.
3. If x matches the middle element, we return the middle position as the index.
4. Else if x is greater than the mid element, set min to the middle index + 1 and go to step 2.
5. Else if x is smaller than the mid element, set max to the middle index – 1 and go to step 2.
6. When min is greater than max, x is not present in the array. Return -1.

One important caveat is that binary search only works on sorted arrays. The reason is that on each iteration, we eliminate half of the remaining search space. This only works if we know the remaining elements are either all smaller or all larger than the target.

Binary Search Complexity

Binary search is very efficient, especially for large lists. In the worst case, binary search will take log₂n iterations to find the target element, where n is the number of elements in the array.

This is a significant improvement over linear search, which requires checking every element in the array one-by-one until the target is found. Linear search has a worst-case time complexity of O(n) – for very large lists, this becomes prohibitively slow.

In terms of space complexity, binary search only requires a couple variables to store the start and end bounds of the search space, so it uses O(1) space.

Binary Search Python Implementation

Now let‘s see how to code binary search in Python. We‘ll look at both iterative and recursive implementations.

Iterative Binary Search

Here is an iterative Python implementation of binary search:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Let‘s walk through this code step-by-step:

1. We define a function called binary_search that takes a sorted array arr and a target value target.

2. We initialize two pointers, low and high, that define the current search space. low starts at 0 (the first index) and high starts at the last index.

3. We enter a while loop that continues as long as low is less than or equal to high. This loop will narrow down the search space on each iteration.

4. Inside the loop, we calculate the index of the middle element by taking the average of low and high using integer division.

5. We then compare the value at the middle index to the target value. If they are equal, we have found the target and return the middle index.

6. If the middle element is less than the target, we know the target must be in the upper half of the search space. So we update low to be mid + 1.

7. If the middle element is greater than the target, we know the target must be in the lower half of the search space. So we update high to be mid - 1.

8. If we exit the loop without finding the target, that means the target is not present in the array. In this case we return -1.

Here‘s an example of using this binary search function:

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print(binary_search(arr, 11))  # Output: 5
print(binary_search(arr, 8))   # Output: -1

In the first example, we search for the number 11 in the sorted array. Binary search correctly returns its index, which is 5.

In the second example, we search for the number 8, which is not present in the array. The function returns -1 to indicate the target was not found.

Recursive Binary Search

We can also implement binary search using recursion. A recursive function is one that calls itself until a certain condition is met.

Here‘s a recursive implementation of binary search in Python:

def recursive_binary_search(arr, low, high, target):
    if low > high:
        return -1

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return recursive_binary_search(arr, mid+1, high, target)
    else:
        return recursive_binary_search(arr, low, mid-1, target)

The basic idea is the same as the iterative version, but instead of using a loop, we use recursive function calls to narrow down the search space.

Here‘s how it works:

1. We define a function called recursive_binary_search that takes the sorted array arr, the current low and high bounds, and the target value.

2. We first check the base case: if low is greater than high, that means we‘ve exhausted the search space without finding the target. In this case we return -1.

3. If the base case is not met, we calculate the middle index mid using integer division.

4. We then compare the value at the middle index to the target. If they are equal, we have found the target and return mid.

5. If the middle element is less than the target, we know the target must be in the upper half of the search space. So we recursively call the function with mid+1 as the new low.

6. If the middle element is greater than the target, we know the target must be in the lower half of the search space. So we recursively call the function with mid-1 as the new high.

7. This process continues until either the target is found or the base case is triggered.

Here‘s an example of using the recursive binary search function:

arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

print(recursive_binary_search(arr, 0, len(arr)-1, 12))  # Output: 5
print(recursive_binary_search(arr, 0, len(arr)-1, 9))   # Output: -1

The usage is similar to the iterative version, but we need to pass the initial low and high values when calling the function.

Practical Applications of Binary Search

Binary search is a fundamental algorithm in computer science with many practical applications. Some common use cases include:

1. Searching in a phone book or dictionary: Given a name, efficiently find the corresponding phone number or dictionary definition by repeatedly dividing the search space in half.

2. Game development: Binary search can be used to quickly locate resources or entities within large game worlds.

3. Database indexing: Many database engines use binary search to quickly locate records within indexed columns.

4. Debugging: When debugging code, binary search can be used to efficiently locate the source of a bug by repeatedly dividing the search space (e.g. line numbers) in half.

5. Numerical analysis: Binary search is often used to find roots of continuous functions and optimization problems.

Whenever you have a large, sorted dataset and need to efficiently locate a specific item, binary search is often a good choice. By leveraging its logarithmic time complexity, binary search enables searching very large datasets extremely quickly.

Conclusion

In this post, we took an in-depth look at the binary search algorithm and how to implement it in Python. We walked through both iterative and recursive code examples and discussed the time and space complexity of binary search compared to other algorithms like linear search.

Binary search is an essential tool in every programmer‘s toolkit. Its "divide and conquer" approach enables efficiently searching very large sorted datasets in logarithmic time.

Whenever you encounter a problem that involves searching for an item in a sorted collection, consider using binary search. With a solid grasp of how the algorithm works and how to implement it, you‘ll be able to write more efficient and scalable code.

I hope this post has been helpful in understanding binary search and how to use it in your own Python projects. Happy coding!