Binary Search Algorithm Explained: From Algorithm To Implementation

Table of Contents

Binary search is a fundamental algorithm in computer science, offering an efficient way to find an item in a sorted array. Unlike linear search, which scans each item in the array sequentially until the target is found, binary search divides and conquers, drastically reducing the number of comparisons needed to locate an item. This makes binary search incredibly efficient, especially for large datasets. In this post, we’ll explore the basics of binary search, how it works, and why it’s such a powerful tool in a programmer’s arsenal.

Binary Search Algorithm

The Main Idea

At its core, binary search operates on a simple principle: by continually dividing the search interval in half, you can quickly narrow down the search space. This method assumes that the array is sorted, which is a critical precondition for binary search to work.

The process begins by comparing the target value to the middle element of the array. If the target value is equal to the middle element, the search is complete. If the target value is less than the middle element, the search continues on the left half of the array. Otherwise, if the target value is greater, the search proceeds on the right half. This process repeats until the target value is found or the search space is exhausted.

Let’s break down the steps involved in implementing binary search:

Initialize: Start with two pointers, one pointing to the start of the array (low) and the other to the end (high).
Find the Middle: Calculate the middle position mid using (low + high) / 2.
Compare: Compare the target value with the element at the mid position.
- If the target is equal to the mid element, you’ve found the target, and the search is complete.
- If the target is less than the mid element, adjust the high pointer to mid - 1 and repeat the process for the left subarray.
- If the target is greater than the mid element, adjust the low pointer to mid + 1 and repeat the process for the right subarray.
Repeat steps 2-3 until the target is found or the low pointer exceeds the high pointer, indicating the target is not in the array.

The following animation will help us understand the concept by watching it visually:

Binary search example animations.

The Importance of Being Sorted

Binary search hinges on the array being sorted to effectively halve the search space with each iteration, based on the assumption that elements are in a known order. This ordering allows it to determine whether the target would be in the left or right half of the current search interval. Without a sorted structure, this decision-making process becomes baseless.

Consider attempting binary search on an unsorted array [5, 2, 8, 3, 1] for the target value 3. Binary search would initially examine the middle element (in this case, 8) and decide to search the left half [5, 2]as $3 < 8$ . We would conclude that our target value 3 does not exist in the array, when it actually does.

Implementation

The algorithm can be implemented iteratively and recursively. While both implementations are very similar to one another, there are a few differences, mainly the space complexity of both. Let’s look at both and compare.

Iterative Implementation

def binary_search(arr, target):
    """
    Performs binary search to find the index of target in arr.
    
    :param arr: Sorted list of elements to search through
    :param target: Target value to find
    :return: Index of target in arr if found, else -1
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is greater, ignore left half
        elif arr[mid] < target:
            low = mid + 1
        # If target is smaller, ignore right half
        else:
            high = mid - 1
    # If we reach here, the element was not present
    return -1

Recursive Implementation

def binary_search_recursive(arr, target, low, high):
    """
    Performs binary search recursively to find the index of target in arr.

    :param arr: Sorted list of elements to search through
    :param target: Target value to find
    :param low: Starting index of the search interval
    :param high: Ending index of the search interval
    :return: Index of target in arr if found, else -1
    """
    if high < low:
        # Element is not present in array
        return -1
    mid = (high + low) // 2

    # If element is present at the middle itself
    if arr[mid] == target:
        return mid
    # If element is smaller than mid, then it can only be present in left subarray
    if arr[mid] > target:
        return binary_search_recursive(arr, target, low, mid - 1)
    # Else the element can only be present in right subarray
    return binary_search_recursive(arr, target, mid + 1, high)

Time Complexity

The most significant advantage of binary search lies in its time complexity of $O(log n)$ , where $n$ is the number of elements in the array. This logarithmic complexity arises because binary search splits the search space in half with each iteration. To put this into perspective:

In an array of 1,000 elements, binary search would find the target in at most 10 comparisons (since $2^{10}=1024$ ).
For an array with a million elements, binary search would require at most 20 comparisons (since $2^{20}=1,048,576$ ).

This efficiency starkly contrasts with linear search, which has a linear time complexity of $O(n)$ , requiring up to $n$ comparisons in the worst case. This difference becomes dramatically significant as the dataset size increases.

Space Complexity

Iterative Implementation Space Complexity

In its iterative form, binary search has a constant space complexity of $O(1)$ , as it requires a fixed amount of space for its variables (like the low, high, and mid pointers), regardless of the array size.

Recursive Implementation Space Complexity

If binary search is implemented recursively, its space complexity becomes $O(log n)$ due to the additional space required for the call stack. Each recursive call adds a layer to the stack, with the depth of recursion proportional to the number of times the array can be halved, which is $log n$ .

Comparison with Linear Search

The efficiency of binary search becomes apparent when compared with linear search, especially for large datasets. While binary search can locate an item in a 1-million-element array with just 20 comparisons, a linear search might need up to 1 million comparisons in the worst case. This difference highlights why binary search is preferred for searching in sorted arrays.

Feature	Linear Search	Binary Search
Prerequisite	No need for the array to be sorted.	Array must be sorted.
Time Complexity	$O(n)$ – Requires scanning each element until the target is found.	$O(log n)$ – Divides the search space in half with each iteration.
Space Complexity	$O(1)$ – Uses a constant amount of space.	Iterative: $O(1)$ , Recursive: $O(log n)$ due to call stack.
Use Case	Effective for small or unsorted datasets.	Preferred for large, sorted datasets.

Comparison table between binary and linear search.

Conclusion

Understanding the complexity of binary search reveals why it’s such an efficient algorithm for searching in sorted arrays. Its logarithmic time complexity ensures that it can handle large datasets with minimal performance degradation.