Binary Search in JS

The plain-language idea

Binary search finds a value in a sorted array by repeatedly checking the middle element and throwing away half the remaining space. If the middle is too big, the answer (if it exists) must be to the left, so discard the right half. If it's too small, discard the left half. Repeat until you find it or run out of space to search.

The one prerequisite that trips people up: the array must already be sorted. Binary search doesn't work on unsorted data — the whole trick depends on being able to say "everything left of here is smaller" and "everything right of here is bigger."

See it in a real thing: searching a sorted array

function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

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

    if (sortedArr[mid] === target) return mid;       // found it
    if (sortedArr[mid] < target) left = mid + 1;      // discard left half, including mid
    else right = mid - 1;                             // discard right half, including mid
  }

  return -1; // not found
}

const nums = [1, 3, 5, 7, 9, 11, 13, 15];
binarySearch(nums, 11); // 5
binarySearch(nums, 4);  // -1

Each pass through the loop cuts the remaining candidates in half. Eight elements takes at most 3 comparisons; a million elements takes at most about 20. That's O(log n) — versus a linear scan (Array.prototype.indexOf, or a plain for loop checking each element) which is O(n): doubling the array roughly doubles the worst-case work, forever.

What people usually miss

Watch out

• mid = Math.floor((left + right) / 2) can overflow in some languages — not really a JS problem, since JS numbers don't overflow the way fixed-width integers do in C or Java, but interviewers often expect left + Math.floor((right - left) / 2) anyway, since it's the safe idiom across languages.
• Updating the wrong boundary re-includes mid and can infinite-loop. After ruling out sortedArr[mid], the next search range must exclude it: left = mid + 1, not left = mid. Forgetting the + 1 (or - 1 on the other side) is the single most common bug in a hand-written binary search.
• It only ever tells you "found" or "not found" for a single sorted array pass — it's not a general search strategy. For "find the leftmost/rightmost matching index" or "find the insertion point for a value that isn't present," the same halving idea applies but the boundary-update logic changes slightly; don't assume one binary search template covers every variant.

The genealogy: divide-and-conquer, and why sortedness is load-bearing

Binary search is the simplest example of a divide-and-conquer strategy — solve a smaller version of the same problem and combine results — the same family sorting algorithms like merge sort and quicksort belong to. It also depends entirely on a precondition (sortedness) rather than any special property of the data itself; the same discipline of stating "this only works if X holds" matters whenever you reach for Array.prototype.reduce to build up a result — the function only behaves correctly if the accumulator's shape matches every step's assumption about it.