Binary Search

Binary Search

Binary Search finds an element in a sorted array by repeatedly halving the search space. Each comparison eliminates half the remaining candidates.

How It Works

Maintain two pointers: lo (start) and hi (end). While lo <= hi:

1. Calculate mid = Math.floor((lo + hi) / 2).
2. If arr[mid] === target, return mid. Found it.
3. If arr[mid] < target, the target must be to the right: set lo = mid + 1.
4. If arr[mid] > target, the target must be to the left: set hi = mid - 1.
5. If the loop ends without finding the target, return -1.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Complexity

Binary search on 1 billion elements needs at most 30 comparisons. Linear search needs up to 1 billion. This is the power of O(log n).

Requirement: The array must be sorted. If you will search many times, sorting once (O(n log n)) and binary searching repeatedly (O(log n) each) is far faster than linear searching each time.

Your Task

Implement binarySearch(arr, target) that returns the index of target in the sorted array arr, or -1 if not found.