Binary Search Explained

Binary search is an efficient algorithm for finding an item from a sorted list of items. It significantly reduces the number of comparisons needed compared to a linear search, making it ideal for large datasets.

How Binary Search Works

Imagine searching for a word in a dictionary. You wouldn't start from the first page and read every word. Instead, you'd open to the middle, see if your word comes before or after, and then repeat the process in the relevant half. Binary search applies this same principle.

First, the algorithm requires the data to be sorted. It then establishes two pointers: `low` at the beginning of the list and `high` at the end. In each step, it calculates the middle index and compares the value at that index with the target value.

If the middle value matches the target, the search is complete. If the target is smaller than the middle value, the algorithm discards the upper half of the list by moving the `high` pointer to `mid - 1`. If the target is larger, it discards the lower half by moving the `low` pointer to `mid + 1`. This process continues, halving the search space with each iteration, until the target is found or the `low` pointer surpasses the `high` pointer, indicating the target is not in the list.

function binary_search(sorted_list, target):
    low = 0
    high = length(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = sorted_list[mid]

        if mid_value == target:
            return mid  // Target found at index mid
        else if mid_value < target:
            low = mid + 1 // Target is in the upper half
        else:
            high = mid - 1 // Target is in the lower half

    return -1 // Target not found

Time Complexity

Binary search has a time complexity of O(log n). This logarithmic complexity means that as the number of items (n) in the list grows, the number of steps required to find an item increases very slowly. For instance, searching a list of a million items might only take about 20 comparisons. In contrast, a linear search has a time complexity of O(n), potentially requiring a million comparisons for the same list.

Key Takeaways

• Binary search requires the input data to be sorted.
• It works by repeatedly dividing the search interval in half.
• It uses `low` and `high` pointers to define the current search space.
• The algorithm achieves a highly efficient O(log n) time complexity.
• This efficiency makes it suitable for searching very large datasets.