Exploring Time and Space Complexities of Binary Search

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half until the element is found or the interval is empty.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half
    return -1  # Target not found

template<typename T>
int binary_search(const vector<T>& arr, T target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid; // Target found
        else if (arr[mid] < target)
            left = mid + 1; // Search in the right half
        else
            right = mid - 1; // Search in the left half
    }
    return -1; // Target not found
}

Best Case Time Complexity: O(1)

The best case occurs when the target element is found at the middle of the array on the first comparison. For example,

Array: 3, 8, 15, 20, 35, 50, 75
Target: 20

In the first iteration, the middle element is checked and matches the target (20). Only one comparison is needed, resulting in a time complexity of O(1).

Worst Case Time Complexity: O(log⁡n)

The worst case occurs when the target element is either not in the array or found after repeatedly halving the search interval until it contains only one element.

Let's look at an example.

Array: 3, 8, 15, 20, 35, 50, 75
Target: 35

The search takes place in the following order:

Here, the algorithm checks elements at every halving step until we reach an interval with a single value. Hence, the time complexity is O(logn).

It's important to note that finding the element in the last interval is the same as not finding the element at all. For example,

Array: 3, 8, 15, 20, 35, 50, 75
Target: 36

The search takes place in the following order:

Like before, we had to check every element at every possible interval until we reached an empty interval. So, the time complexity is O(logn).

Average Case Time Complexity: O(log⁡n)

The average-case time complexity also follows a logarithmic trend since the element may be located at any position in the array, and the algorithm always halves the search space in each step.

Space Complexity of Binary Search: O(1)

Binary search is an in-place algorithm requiring no extra memory beyond a few variables for indices and comparisons. The memory usage remains constant regardless of the input size.

Hence, the space complexity of binary search is O(1).

Summary: Time and Space Complexity

When to Use Binary Search?

Binary search is suitable for sorted data and excels in scenarios where efficiency is critical.

When to Use:

• Large Sorted Datasets: The logarithmic time complexity makes binary search very efficient for large data.
• Frequent Lookups: The algorithm is great for applications that require frequent lookups, as long as the data is static (unchanging).

When to Avoid:

1. Unsorted Data: Binary search requires the data to be sorted. For unsorted datasets, linear search or other approaches might be more appropriate.
2. Small Datasets: The overhead of dividing the search interval might make linear search faster for very small arrays.