LiveCodingInterview.com
← Articles

Binary Search Algorithm: A Coding Interview Guide

Binary search is one of the highest-leverage patterns in coding interviews. Once you recognize "sorted input" or "find boundary in monotonic space," you can often drop from O(n) to O(log n) — and interviewers will expect you to.

This guide covers the core idea, two standard implementations, and the follow-ups that separate a passing answer from a strong one.

When linear search is enough

The straightforward way to find a value in an array is a single loop:

function linearSearch(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) return i;
  }
  return -1;
}

Time complexity: **O(n)** — in the worst case you inspect every element. If the array is unsorted and you have no extra structure, that is optimal. There is no shortcut without additional information.

Why sorting unlocks O(log n)

When the array is **sorted ascending**, order tells you where to look next. Compare against the middle element:

  • Equal → found
  • Target is smaller → search the left half only
  • Target is larger → search the right half only

Each comparison eliminates half the remaining elements. That halving is what gives **O(log n)** time.

Interview tip: say this out loud before coding — "I'll maintain a search range and cut it in half each step."

Think of looking up a word in a dictionary. You keep an active range `[lo, hi]` that starts as the full array. Repeatedly inspect the midpoint and narrow to the left or right half.

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

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

    if (arr[mid] === x) return mid;
    if (arr[mid] > x) hi = mid - 1;
    else lo = mid + 1;
  }

  return -1;
}

The active region shrinks by at least half each iteration, so the loop runs at most **⌈log₂(n + 1)⌉** times → **O(log n)**.

Avoid integer overflow

In languages like Java or C++, `lo + hi` can overflow. Use `lo + (hi - lo) / 2` (shown above). In JavaScript numbers are doubles so overflow is rare, but interviewers still like hearing you know the idiom.

Loop invariant to remember

When the loop ends with `lo > hi`, the target is not present. Some variants use `lo < hi` for "first position where…" problems — know which template you are using and stick to it.

Method 2: Jump search with shrinking step size

A second pattern scans left to right but jumps in large steps, then halves the jump size as you hone in — like galloping across the array and slowing down near the target.

Start with jump length `b = ⌊n/2⌋`. For each jump size (n/2, n/4, n/8, … down to 1), advance the pointer while the landing spot is still safe and not past the target. After all jumps, check the final index.

function binarySearchJump(arr, x) {
  const n = arr.length;
  let k = 0;

  for (let b = Math.floor(n / 2); b >= 1; b = Math.floor(b / 2)) {
    while (k + b < n && arr[k + b] <= x) {
      k += b;
    }
  }

  if (arr[k] === x) return k;
  return -1;
}

The inner `while` moves `k` forward at most once per jump level, and there are O(log n) levels — still **O(log n)** overall.

This variant is less common in live coding but useful for **lower bound** style problems (first index where value ≥ x). Many standard libraries expose this as `bisect_left` / `lower_bound`.

Beyond "find exact value"

Interviewers rarely ask for vanilla search on a plain array. They ask variants:

  • **First / last occurrence** of x in a sorted array with duplicates
  • **Search in rotated sorted array**
  • **Find peak / minimum in rotated array**
  • **Binary search on answer** — monotonic predicate over the answer space (e.g. "minimum capacity to ship packages in D days")

The template changes slightly, but the engine is the same: maintain a range, discard half based on a comparison.

Complexity summary

  • **Linear scan** — unsorted OK, O(n) time, O(1) space
  • **Binary search (Method 1)** — sorted required, O(log n) time, O(1) space
  • **Jump binary (Method 2)** — sorted required, O(log n) time, O(1) space

Recursive binary search uses O(log n) call stack space — mention that if you implement it recursively instead of iteratively.

Common mistakes in interviews

  • Forgetting to handle **empty array** or single-element edge cases
  • Off-by-one errors on `hi = mid - 1` vs `hi = mid` in lower-bound templates
  • Using binary search on unsorted data without sorting first (adds O(n log n) preprocessing)
  • Infinite loops when `lo` and `hi` do not converge — test with 2-element arrays

How to practice

  1. Implement Method 1 from memory on a whiteboard.
  2. Solve "find first and last position of element" on LeetCode-style platforms.
  3. Apply the coding interview framework — clarify sorted order, walk an example, then code.
  4. State **O(log n)** time and **O(1)** extra space before you run test cases.

Implementations by language

More algorithm guides