Binary Search

Binary search finds a value in a sorted array by repeatedly looking at the middle element and throwing away the half that can't contain the target. Each step halves the work, so even a million elements take only ~20 comparisons.

The loop, step by step

1. 1Track a window with lo and hi (start: the whole array).
2. 2Look at the middle: mid = (lo + hi) / 2.
3. 3If arr[mid] equals the target → found.
4. 4If arr[mid] is less than the target → the answer is to the right, so lo = mid + 1.
5. 5If arr[mid] is greater → the answer is to the left, so hi = mid - 1.
6. 6Repeat until found or the window is empty (lo > hi).

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; // not found
}