Binary Search

Introduction and Purpose

Binary search is a technique for finding a target value inside a sorted collection. Instead of checking every element one by one, it starts at the middle, asks "is the target before or after this?", and eliminates half of the remaining candidates in one step. Repeat until found — or until nothing is left.

The payoff is dramatic: searching 1,000,000 elements takes at most 20 comparisons. Linear search would take up to 1,000,000. This O(log n) behaviour is one of the most impactful ideas in programming.

Problems Addressed

The dictionary analogy explains it perfectly. You never find a word in a dictionary by reading from page 1. You open to roughly the middle, see whether your word comes before or after, flip to the middle of that half, and repeat. You reach the word in a handful of steps regardless of how thick the book is.

Binary search applies whenever you can answer the question "should I go left or right?" at each step. That covers more ground than just "find an element":

• Exact search: Is value X in this sorted array?
• Boundary search: What is the first index where the condition becomes true?
• Search on the answer: What is the smallest value of X that satisfies a constraint?
• Searching in disguise: Problems that don't look like search but reduce to one (square roots, rotated arrays, peak finding).

Why sorted order is mandatory

Binary search only works when the data is sorted (or at least monotonic — consistently going one direction). If the data is unsorted, eliminating half the candidates is invalid — the target could be anywhere.

Common Approaches

Approach 1: Classic iterative binary search

The standard pattern. Two pointers (lo and hi) define the current search window. Each iteration checks the midpoint and moves one of the pointers to shrink the window.

Tracing a search for 19 in [2, 5, 8, 12, 19, 24, 31]:

Step	lo	hi	mid	array[mid]	Decision
1	0	6	3	12	19 > 12 → go right
2	4	6	5	24	19 < 24 → go left
3	4	4	4	19	Found!

3 steps for 7 elements. Linear search would take up to 7.

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);

    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1; // target is in the right half
    else hi = mid - 1;                    // target is in the left half
  }

  return -1; // not found
}

const arr = [2, 5, 8, 12, 19, 24, 31];
console.log(binarySearch(arr, 19));  // 4
console.log(binarySearch(arr, 10));  // -1

Time: O(log n). Space: O(1).

One subtle but important implementation detail: computing mid as Math.floor((lo + hi) / 2) is safe in JavaScript. In languages with fixed-size integers (Java, C++), (lo + hi) can overflow for large arrays — the safe form there is lo + Math.floor((hi - lo) / 2).

---

Approach 2: Finding the left boundary (first occurrence)

When duplicates exist, the classic search stops at any matching index. To find the first occurrence, keep going left even after a match.

function findFirst(nums, target) {
  let lo = 0, hi = nums.length - 1;
  let result = -1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);

    if (nums[mid] === target) {
      result = mid;  // Record the match...
      hi = mid - 1;  // ...but keep searching left
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

const arr = [1, 2, 2, 2, 3, 4];
console.log(findFirst(arr, 2)); // 1 (index of the first 2)

Approach 3: Finding the right boundary (last occurrence)

Mirror image of the above — keep going right after a match.

function findLast(nums, target) {
  let lo = 0, hi = nums.length - 1;
  let result = -1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);

    if (nums[mid] === target) {
      result = mid;  // Record the match...
      lo = mid + 1;  // ...but keep searching right
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

const arr = [1, 2, 2, 2, 3, 4];
console.log(findLast(arr, 2)); // 3 (index of the last 2)

// Count occurrences by combining both
function countOccurrences(nums, target) {
  const first = findFirst(nums, target);
  if (first === -1) return 0;
  return findLast(nums, target) - first + 1;
}

console.log(countOccurrences(arr, 2)); // 3

---

Approach 4: Binary search on the answer

This is the most powerful — and most underrated — form of binary search. Instead of searching in an array, you search for a number that satisfies a condition.

The pattern:

1. Define a range [lo, hi] for the answer.
2. Write a function feasible(mid) that returns true if mid is a valid answer.
3. Binary search for the smallest (or largest) value where feasible is true.

This works whenever feasible is monotonic: once it becomes true, it stays true (or vice versa) as the candidate grows.

Example — Koko Eating Bananas (LeetCode #875): Koko has n piles of bananas and h hours. She eats at speed k bananas/hour, finishing one pile before moving to the next. Find the minimum k that lets her finish all piles in time.

The key insight: if she can finish at speed k, she can definitely finish at any speed > k. So the valid speeds form a monotonic range — binary search works.

function minEatingSpeed(piles, h) {
  // At minimum speed 1, at maximum speed = largest pile (finishes in 1 hour)
  let lo = 1, hi = Math.max(...piles);

  function feasible(speed) {
    // Can Koko finish all piles at this speed within h hours?
    let hoursNeeded = 0;
    for (const pile of piles) {
      hoursNeeded += Math.ceil(pile / speed);
    }
    return hoursNeeded <= h;
  }

  // Find the leftmost (minimum) speed where feasible is true
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(mid)) hi = mid; // mid works, try smaller
    else lo = mid + 1;           // mid doesn't work, need faster
  }

  return lo;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30

Once you see this pattern, many interview problems reveal themselves as binary search in disguise: allocating bandwidth, finding a threshold, minimizing a maximum value.

---

Real-world example: autocomplete with prefix search

Binary search shines in read-heavy lookup systems. Given a sorted dictionary, find all words starting with a prefix in O(log n + k) where k is the number of results.

function prefixRange(words, prefix) {
  // Find first word >= prefix
  function lowerBound() {
    let lo = 0, hi = words.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (words[mid] < prefix) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  // Find first word > prefix + largest possible suffix (using prefix + '{')
  // '{' comes after 'z' in ASCII, so this catches all prefix matches
  function upperBound() {
    const upper = prefix + '{';
    let lo = 0, hi = words.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (words[mid] <= upper) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  return words.slice(lowerBound(), upperBound());
}

const dictionary = ['apple', 'application', 'apply', 'apt', 'banana', 'band', 'bandana'];
console.log(prefixRange(dictionary, 'app')); // ['apple', 'application', 'apply']
console.log(prefixRange(dictionary, 'ban')); // ['banana', 'band', 'bandana']

Complexity Comparison

n	Linear (worst case)	Binary (worst case)
100	100	7
10,000	10,000	14
1,000,000	1,000,000	20
1,000,000,000	1,000,000,000	30

The catch: the data must be sorted. Sorting costs O(n log n). If you only search once, a linear scan may be cheaper. Binary search earns its keep when you sort once and search many times.

Related Algorithms and Data Structures

• Two Pointers: Often confused with binary search — both use two indices on a sorted array, but two pointers move toward each other while binary search shrinks a window around a midpoint.
• Divide & Conquer: Binary search is the simplest example of divide-and-conquer: split the problem in half, solve one half, discard the other.
• Binary Search Trees (BST): Apply the same "go left or right" logic structurally — the tree shape encodes the sorting order.
• Longest Increasing Subsequence: The O(n log n) LIS algorithm uses binary search on the tails array — see LIS article for details.
• Ternary Search: For unimodal (single-peak) functions, divide the range into thirds instead of halves. Less common in interviews but useful in optimization problems. Search for "ternary search competitive programming" for examples.

Tests and Challenges

These problems build the skill progressively — start with #704 and do them in order:

Difficulty	Problem	Platform	What it tests
Easy	Binary Search	LeetCode #704	Classic exact search
Easy	Search Insert Position	LeetCode #35	Left boundary variant
Easy	Ice Cream Parlor	HackerRank	Search in a sorted structure
Medium	Find First and Last Position	LeetCode #34	Left + right boundary
Medium	Find Minimum in Rotated Sorted Array	LeetCode #153	Modified sorted structure
Medium	Koko Eating Bananas	LeetCode #875	Binary search on the answer
Medium	Capacity to Ship Packages	LeetCode #1011	Binary search on the answer
Hard	Median of Two Sorted Arrays	LeetCode #4	Advanced binary search logic

A reliable study path: solve #704 → #35 → #34 in sequence. They teach the three core variants (exact, left bound, right bound) using the same array. Once those feel automatic, #875 and #1011 introduce the "search on the answer" pattern which is the most interview-relevant form.

Related Concepts

• Big O Notation — The O(log n) complexity of binary search is explained in depth here, including why halving leads to logarithmic growth.
• Longest Increasing Subsequence — Uses binary search internally in its O(n log n) solution; a good example of binary search applied outside of direct lookup.
• Dynamic Programming — The "search on the answer" pattern (Approach 4) sits at the boundary between binary search and DP optimization; many DP problems gain an O(log n) factor by searching for the optimal value rather than trying every candidate.