What is the time complexity of a binary search algorithm?

Binary search is a highly efficient algorithm used to find a target value within a sorted array. It operates by repeatedly dividing the search interval in half. The core idea is to compare the target value with the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until the target is found or the interval becomes empty.

Worst-Case Time Complexity: O(log n)

The worst-case time complexity of binary search is O(log n). This occurs when the target element is either not present in the array or is found only after many divisions of the search space. In each step, the algorithm halves the size of the search space. If the initial size of the array is 'n', after one comparison the size becomes n/2, then n/4, and so on, until the size is 1. The number of steps required to reach 1 from 'n' by repeatedly dividing by 2 is approximately log₂n. This logarithmic behavior makes binary search exceptionally fast for large datasets.

Best-Case Time Complexity: O(1)

The best-case time complexity of binary search is O(1). This scenario happens when the target element is located at the middle of the array on the very first comparison. The algorithm finds the element immediately, requiring only a constant amount of time regardless of the array's size.

Average-Case Time Complexity: O(log n)

The average-case time complexity for binary search is also O(log n). On average, the algorithm will still perform a logarithmic number of comparisons to find an element or determine its absence. The halving of the search space at each step dominates the average performance, leading to the same logarithmic complexity as the worst case.

Summary of Time Complexities

• Best Case: O(1) - Target found at the middle on first try.
• Worst Case: O(log n) - Target found at an extreme end or not present.
• Average Case: O(log n) - Average number of comparisons.

Example Implementation (Python)

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # Element found
        elif arr[mid] < target:
            low = mid + 1 # Search in the right half
        else:
            high = mid - 1 # Search in the left half

    return -1 # Element not found