Binary Search

Binary search is a fundamental algorithm for quickly finding a target value within a sorted array. It significantly outperforms linear search by repeatedly halving the search space, making it highly efficient for large datasets.

How Binary Search Works

Binary search operates on the principle that if an array is sorted, you can eliminate a large portion of the array from consideration in each step. This process continues until the target is found or the search space is exhausted.

1. Initialize Pointers

Begin by setting two pointers: `L` (left) at the start of the array (index 0) and `R` (right) at the end of the array (index `len(nums) - 1`). These pointers define the current search interval.

2. Calculate Middle Index

In each iteration, calculate the middle index `M` using the formula `M = (L + R) // 2`. This `M` points to the element that will be compared against the target.

3. Compare and Adjust Search Space

Compare the value at `nums[M]` with the `target`:

• If `nums[M]` equals the `target`, the element is found, and its index `M` is returned.
• If `nums[M]` is less than the `target`, the target must be in the right half of the current search space (since the array is sorted). The `L` pointer is updated to `M + 1` to exclude the left half and the middle element.
• If `nums[M]` is greater than the `target`, the target must be in the left half. The `R` pointer is updated to `M - 1` to exclude the right half and the middle element.

This process repeats, narrowing the search interval, until `L` crosses `R` (meaning `L > R`), at which point the target is not in the array.

def search(nums, target):
    L, R = 0, len(nums) - 1
    while L <= R:
        M = (L + R) // 2
        if nums[M] == target:
            return M
        elif nums[M] < target:
            L = M + 1
        else:
            R = M - 1
    return -1

Key Takeaways

• Binary search requires the input array to be sorted.
• It works by repeatedly dividing the search interval in half.
• The time complexity is O(log n), making it very efficient.
• Pointers `L` and `R` define the current search boundaries.
• The algorithm terminates when the target is found or the search space is empty.