Binary Search

Binary Search is a foundational algorithm for finding a target value within a sorted array. It works by repeatedly comparing the target to the middle element of the array.

Imagine finding a word in a dictionary. You don't read every word from the start (Linear Search). Instead, you open the book to the middle. If the target word is alphabetically after the middle, you discard the first half and search the second half. You repeat this until you find the word.

The simplest way is to check every element from left to right.

function search(nums: number[], target: number): number {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) return i;
    }
    return -1;
}

Why it fails

• Time Complexity: O(n). If the array helps 1 billion elements, you might make 1 billion comparisons.
• Inefficient: It ignores the fact that the array is sorted.

Since the array is sorted, we can rule out half of the elements in one step.

1. Pick the middle element.
2. If middle === target, we are done.
3. If middle < target, the target must be in the right half (all elements to left are simpler).
4. If middle > target, the target must be in the left half.
5. Repeat on the smaller subarray.