Binary Search

Halve the search space each step to find an element or boundary in O(log n).

10 problems 1 Easy 7 Medium 2 Hard

Overview

Binary search applies wherever the search space has a monotonic property — not just sorted arrays. The key insight is identifying the correct invariant and boundary conditions.

When to Use

Searching in sorted array
Finding first/last occurrence
Binary search on answer (min max problems)
Rotated sorted array search
Koko eating bananas style problems

Common Mistakes

Integer overflow with mid = (left + right) / 2 — use left + (right - left) / 2
Wrong boundary: while left < right vs while left <= right
Off-by-one when updating left/right

Complexity

Time

O(log n)

Space

O(1) iterative, O(log n) recursive

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

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// Binary search on answer template
function binarySearchAnswer(lo, hi) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Problems (10)

Hide completed

Problem	Difficulty	Companies	Freq
Binary Search	Easy	AmazonGoogle +1	High
Search in Rotated Sorted Array	Medium	AmazonFacebook +2	High
Find Minimum in Rotated Sorted Array	Medium	AmazonMicrosoft	High
Koko Eating Bananas	Medium	FacebookAmazon	Medium
Find Peak Element	Medium	GoogleFacebook	Medium
Time Based Key-Value Store	Medium	GoogleAirbnb	Medium
Search a 2D Matrix	Medium	AmazonMicrosoft +1	High
Capacity to Ship Packages Within D Days	Medium	AmazonFacebook +1	High
Split Array Largest Sum	Hard	GoogleFacebook +1	Medium
Median of Two Sorted Arrays	Hard	GoogleAmazon +3	High

Binary search is not just for sorted arrays. The answer-space variant unlocks a whole class of "mini…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee

Buy me a coffee