Binary Search

Binary Search is one of the most fundamental algorithms in computer science, widely used for efficiently searching in sorted structures. Its core idea is simple yet powerful: instead of scanning every element linearly, it repeatedly divides the search space in half, reducing the problem size exponentially at each step. This leads to a time complexity of $O(\log n)$, which is significantly faster than a linear scan for large datasets.

The algorithm

The algorithm works on the principle of divide and conquer. Given a sorted array, we compare the target element with the middle element. If the target equals the middle element, the search terminates successfully. If the target is smaller, the search continues in the left half; if larger, in the right half. This halving continues until the search space becomes empty or the element is found.

Here is a canonical TypeScript implementation:

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Several subtle but important details are worth noting:

• the calculation of mid as left + (right - left) / 2 prevents integer overflow, which can occur if left + right exceeds the maximum integer value. While JavaScript/TypeScript numbers are safe, this is critical in languages like Java or C++.
• Binary Search requires a sorted structure; using it on an unsorted array will lead to incorrect results.
• The algorithm naturally lends itself to recursion, though iterative implementations are usually preferred for efficiency and avoiding stack overflow.

Binary Search is more than just a search algorithm. It forms the foundation for numerous patterns and problem-solving techniques, including:

• Finding insertion positions in arrays
• Detecting boundaries like first or last occurrences
• Searching in rotated or partially sorted arrays
• Solving “search the answer” problems where the solution space is numerical or monotonic

All these variations can be tackled with a few core adaptations of the basic Binary Search. For example, to search on rotated sorted arrays, we can modify the comparison logic to determine which half is properly sorted and adjust our search accordingly.

function search(nums: number[], target: number): number {
    let left = 0
    let right = nums.length - 1

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)

        if (nums[mid] === target) {
            return mid
        }

        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left  = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
};

Time and Space Complexity

Binary Search works by repeatedly halving the search space until the target element is found or the space becomes empty. At each step, only a single comparison is performed, resulting in very efficient logarithmic behavior.

The number of iterations depends on the size of the input array:

• In all cases, the search space is halved at each step, so the number of iterations is $O(\log n)$.

For this reason:

• Average time complexity: $O(\log n)$
• Worst-case time complexity: $O(\log n)$

For what concerns space complexity, Binary Search can be implemented iteratively with no extra memory allocation:

• Auxiliary space: $O(1)$
• Recursion stack (if implemented recursively): $O(\log n)$

As a result:

• Average space complexity: $O(1)$ iterative, $O(\log n)$ recursive
• Worst-case space complexity: $O(1)$ iterative, $O(\log n)$ recursive

Exercises