Binary Search Pattern

Why this pattern matters for LeetCode

A linear scan checks every element — 1 million elements means up to 1 million comparisons. Binary Search works on sorted data by cutting the search space in half each step. 1 million elements takes at most 20 steps. The challenge is getting the boundary conditions right — most Binary Search bugs are off-by-one errors in the loop condition or the pointer updates. Get the template right once and reuse it.

What the Binary Search pattern is

Binary search works by comparing the midpoint to the target. If it matches, you're done. If the target is smaller, discard the right half. If larger, discard the left half. Each step eliminates half the remaining candidates, giving O(log n) time. The pattern extends beyond simple value lookup: you can binary search on the answer to find the smallest value that satisfies a condition.

Reach for Binary Search when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Binary Search

• ✓Finding a target value in a sorted array (classic Binary Search)
• ✓Finding the insert position for a value in a sorted array
• ✓Finding the first or last occurrence of a target
• ✓Finding the minimum in a rotated sorted array
• ✓Binary searching on the answer — finding the smallest/largest value that satisfies a condition

When NOT to use Binary Search

• ✕The input is unsorted and sorting it would be O(n log n) — which negates the log n benefit
• ✕You need to find all occurrences — binary search finds one, you'd still need to scan
• ✕The input is small enough that linear scan is fine and simpler to write
• ✕The condition isn't monotonic — binary search only works if one half always satisfies the condition

Better alternative: In those cases, a linear scan or Two Pointers may be simpler and correct.

JavaScript code template

Binary search template — O(log n) time, O(1) space

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

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

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

  return -1; // not found
}

left and right define the current search space. Each iteration computes mid and compares. If the target is larger than mid, the left half is eliminated. If smaller, the right half is eliminated. When left > right, the space is empty and the target isn't present. The key is mid + 1 and mid - 1 — these ensure mid is excluded from the next iteration and you never get stuck in an infinite loop.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Set left = 0 and right = nums.length - 1.
2. 2While left <= right: compute mid = left + Math.floor((right - left) / 2).
3. 3Compare nums[mid] to the target.
4. 4If equal, return mid — found it.
5. 5If nums[mid] < target, move left to mid + 1 (discard left half including mid).
6. 6If nums[mid] > target, move right to mid - 1 (discard right half including mid).
7. 7If the loop ends without returning, the target isn't in the array — return -1.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Binary Search

  The textbook case — find a target value in a sorted array using the standard template.

  Premium→
• Search Insert Position

  Binary search with a twist: return the insertion index if the target isn't found (left is the answer after the loop).

  Premium→
• Find Minimum in Rotated Sorted Array

  Modified binary search — decide which half the minimum lives in based on comparing to the right boundary.

  Premium→
• Search in Rotated Sorted Array

  Determine which half is sorted, then decide which half the target must be in.

  Premium→
• Koko Eating Bananas

  Binary search on the answer — find the minimum eating speed that finishes within h hours.

  Premium→
• First Bad Version

  Binary search on a boolean condition — find the boundary where isBadVersion flips from false to true.

  Premium→

Common mistakes beginners make

• ✕left < right vs left <= right — use <= for standard search where mid needs to be compared. Use < for boundary-finding variants where you want left to land on the answer.
• ✕Setting right = mid instead of mid - 1 — this can cause an infinite loop when left and right are adjacent.
• ✕Integer overflow in other languages: (left + right) can overflow a 32-bit integer. Always prefer left + Math.floor((right - left) / 2).
• ✕Applying binary search to an unsorted array — it will silently produce wrong answers with no error.

Binary Search vs Two Pointers

Choose the right tool for the job.

Time and space complexity

Each iteration halves the search space. Starting from n elements, after 1 step you have n/2, after 2 steps n/4, and so on. After log₂(n) steps you have 1 element. So the loop runs at most log₂(n) times — O(log n). Only two integer variables (left and right) are needed, so space is O(1).

Frequently asked questions

When should I use left <= right vs left < right?

Use left <= right for the standard value-search template where you're looking for an exact match and return early when found. Use left < right for boundary-finding variants (first/last occurrence, Search Insert Position) where you want left to converge to the answer after the loop — in those, you adjust mid comparison and set right = mid (not mid - 1).

Why do off-by-one errors happen so often in Binary Search?

Because the boundary conditions (<= vs <, mid-1 vs mid, mid+1 vs mid) all affect whether you include mid in the next search range and whether the loop terminates correctly. A wrong boundary can cause infinite loops or skip the answer. Stick to one proven template and adapt it carefully.

When should I use Binary Search instead of a linear scan?

When the input is sorted and n is large enough that O(n) is too slow. For small arrays (under ~100 elements), the difference is negligible and a linear scan is simpler to write and debug. For n = 10⁶, binary search takes ~20 steps; linear scan takes up to a million.

What's the integer overflow issue and does it affect JavaScript?

In Java and C++, (left + right) can overflow a 32-bit integer if both are near INT_MAX. JavaScript uses 64-bit floats so it rarely overflows in practice. But left + Math.floor((right - left) / 2) is still the safer and more portable habit to build.

Can Binary Search work on things other than arrays?

Yes — it works on any monotonic answer space. Koko Eating Bananas and similar problems binary search on a range of possible answers (eating speeds, days, sizes) rather than an array. If you can write a condition like 'can X satisfy the constraint?' and the answer changes from false to true (or true to false) at some threshold, you can binary search for that threshold.