Binary Search Pattern: Find Any Value in O(log N)

Story Time

The Paper Dictionary 📖

Before writing a single line of code, let's understand the intuition through a story.

📖

Priya Looks Up a Word

Priya has a paper dictionary with roughly 100,000 entries and needs to find meridian. The entries are already in alphabetical order — that ordering is about to do all the work.

😩

The Exhausting Way

Nobody reads a dictionary from aardvark forward, but that is exactly what a linear scan does — check entry 1, then entry 2, then entry 3. On average it reads half the book: 50,000 entries. That is O(N), and it completely wastes the fact that the book is alphabetised.

🧙

What She Actually Does

She flops the book open near the middle and lands on lantern. Meridian comes after lantern, so the entire first half of the book is now irrelevant — not skimmed quickly, but never opened again. She repeats the same move on what is left.

✗ Linear scan: read entries one by one → O(N)
✓ Binary search: halve the candidates each time → O(log N)

📉

How Fast Halving Really Is

Each comparison cuts the candidate pile in half. Watch 100,000 entries disappear:

Start 100,000 candidates left — the whole book is a candidate

1 look 50,000 candidates left — half the book, gone

5 looks 3,125 candidates left — 97% eliminated

10 looks 98 candidates left — a few pages left

17 looks 1 candidates left — found it ✓

🚀

Moral of the story

When data is ordered, one comparison can rule out half of everything that is left. Seventeen comparisons beat fifty thousand — and doubling the dictionary to 200,000 entries costs exactly one more step.

Interactive

Halving Visualizer

Search [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] for 23. Ten candidates, three comparisons.

candidates: 10

Start: L=[0], R=[9], mid=[4]. nums[4] = 16 < 23, so discard mid and everything left of it → L = 5.

still a candidate mid — being compared target found eliminated

mid = left + (right - left) / 2 Pick the middle candidate

nums[mid] < target → left = mid + 1 Too small — discard the left half

nums[mid] > target → right = mid - 1 Too big — discard the right half

Complexity

Three Approaches

Approach	Time	Space	Best for
Linear Scan	O(N)	O(1)	Unsorted input, tiny arrays
Hash Set / Map	O(1) avg	O(N)	Repeated exact lookups, order irrelevant
Binary Search Preferred ✓	O(log N)	O(1)	Sorted input, boundaries, ranges

A hash set beats binary search on raw lookup speed, but it answers exactly one question: is this value present? Binary search also answers where would it go, what is the nearest value, and where does this run of duplicates start — because it preserves ordering. That is why sorted structures still win for range queries.

TypeScript

Implementation

Exact match → insertion point → boundary.

// Binary Search (exact match) — O(log N) time, O(1) space
// LeetCode 704 — Binary Search
function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;   // inclusive bound → pairs with <=

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

    if (nums[mid] === target) return mid;  // any hit will do
    if (nums[mid] < target) left = mid + 1;   // discard mid and everything left
    else right = mid - 1;                 // discard mid and everything right
  }
  return -1;
}

// [-1, 0, 3, 5, 9, 12], target = 9
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9)); // → 4
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 2)); // → -1

// Binary Search (insertion point) — O(log N) time, O(1) space
// LeetCode 35 — Search Insert Position
function searchInsert(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  // The loop can only exit with left === right + 1.
  // Everything below left was proven too small, everything
  // from left up was proven too large — so left is the slot.
  return left;
}

console.log(searchInsert([1, 3, 5, 6], 5)); // → 2 (found)
console.log(searchInsert([1, 3, 5, 6], 2)); // → 1 (insert here)
console.log(searchInsert([1, 3, 5, 6], 7)); // → 4 (past the end)

// Binary Search (boundary) — O(log N) time, O(1) space
// LeetCode 34 — Find First and Last Position. Full debugging journey:
// /learn/dsa/binary-search/find-first-and-last-position-of-element-in-sorted-array
function findBoundary(
  nums: number[], target: number, findFirst: boolean,
): number {
  let left = 0;
  let right = nums.length - 1;
  let answer = -1;             // the not-found result

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

    if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1;
    else {
      answer = mid;                // record — do NOT return
      if (findFirst) right = mid - 1;  // an earlier hit may exist
      else left = mid + 1;             // a later hit may exist
    }
  }
  return answer;
}

function searchRange(nums: number[], target: number): number[] {
  return [
    findBoundary(nums, target, true),
    findBoundary(nums, target, false),
  ];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // → [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // → [-1, -1]

Want the full debugging story behind findBoundary() — six real bugs, two infinite loops, and how each was found? Read the Find First and Last Position case study.

Comparison

Exact Match vs Boundary

Same loop, one difference: what happens when nums[mid] === target.

🎯 Exact Match returns on hit

On a match return mid immediately

Answers Does the target exist?

Duplicates Returns an arbitrary one

Typical problems LC 704, LC 33

Loop ends Early, on the first hit

📍 Boundary records and continues

On a match answer = mid, then keep shrinking

Answers Where does the run of targets start/end?

Duplicates Handled precisely — that's the point

Typical problems LC 34, LC 35, LC 278

Loop ends Always runs to a closed window

The boundary variant generalises further than it first looks. Replace nums[mid] === target with any monotonic predicate — false, false, …, false, true, true, … — and the same loop finds the flip point. That is how LC 278 First Bad Version and LC 875 Koko Eating Bananas work with no array at all.

Practice

Solve It Yourself

Click any question to see hints and approach.

B Basic

B1 What is the Binary Search pattern, and what does it require of the input? ⌄

💡 Hint

Think about what a single comparison can rule out. What property must the data have for one comparison to eliminate more than one element?

✅ Answer

Binary search repeatedly compares the target to the middle of a candidate window and discards the half that cannot contain it. It requires the input to be sorted (or, more generally, to have a monotonic property), because discarding half is only sound if one comparison genuinely rules that half out. Cost: O(log N) time, O(1) extra space iteratively.

B2 Trace binarySearch([-1, 0, 3, 5, 9, 12], target = 9) step by step. ⌄

💡 Hint

Start with left = 0 and right = 5. Compute mid, compare, and move whichever pointer the comparison licenses.

✅ Answer

left=0, right=5 → mid=2, nums[2]=3 < 9 → left=3. left=3, right=5 → mid=4, nums[4]=9 → match, return 4. Two comparisons for a six-element array.

B3 Why does right = nums.length - 1 pair with while (left <= right), and not while (left < right)? ⌄

💡 Hint

Ask what the window [left, right] contains when left and right are equal.

✅ Answer

With an inclusive right bound, left === right still describes a live one-element window. Using < exits before examining it, so binarySearch([8], 8) returns -1. The half-open convention (right = nums.length) pairs with < instead. Pick one convention and never mix them — mixing is the single most common binary search bug.

M Intermediate

M1 LeetCode 704 — Binary Search: find 9 in [-1, 0, 3, 5, 9, 12], returning -1 if absent. ⌄

💡 Hint

The textbook form. Inclusive bounds, while (left <= right), and return as soon as nums[mid] matches.

✅ Answer

Returns 4. When the target is absent — say 2 — the window closes with left > right and the function returns -1 after at most ⌈log₂(6)⌉ = 3 comparisons.

→ Solve on LeetCode ↗

M2 LeetCode 35 — Search Insert Position: where does 2 belong in [1, 3, 5, 6]? ⌄

💡 Hint

Run a normal binary search. When it fails, one of the two pointers is already sitting on the answer — work out which, and why.

✅ Answer

Index 1. The loop can only exit with left === right + 1; everything below left was proven smaller than the target and everything from left up was proven larger, so left is exactly the insertion slot. Returns 2 for target 5 (found), 4 for target 7 (past the end), and 0 for target 0.

→ Solve on LeetCode ↗

M3 LeetCode 34 — Find First and Last Position: locate both ends of the 8s in [5, 7, 7, 8, 8, 10]. ⌄

💡 Hint

One binary search ends holding one index, but you need two. On a match, don't return — record the index and keep shrinking toward the side you want.

✅ Answer

[3, 4]. Run the loop twice: once biased left (on a match, right = mid - 1) for the first occurrence, once biased right (on a match, left = mid + 1) for the last. Two O(log N) searches is still O(log N). This exact problem has a full worked debugging journey — six real bugs, including two infinite loops — on the case study page.

→ Read the full case study

H Advanced

H1 LeetCode 33 — Search in Rotated Sorted Array: find 0 in [4, 5, 6, 7, 0, 1, 2]. ⌄

💡 Hint

The array is sorted but rotated at an unknown pivot. A single rotation point cannot sit in both halves — so after splitting at mid, at least one half is still cleanly sorted. Identify it by comparing endpoints.

✅ Answer

Index 4. left=0,right=6 → mid=3 (7); nums[0]=4 ≤ 7 so the left half is sorted, but 0 is not in [4,7) → search right, left=4. left=4,right=6 → mid=5 (1); nums[4]=0 ≤ 1 so the left half is sorted and 0 is in [0,1) → search left, right=4. left=4,right=4 → mid=4 (0) → match. Still O(log N) — no un-rotating pass needed.

→ Solve on LeetCode ↗

H2 LeetCode 875 — Koko Eating Bananas: with piles [3, 6, 7, 11] and h = 8 hours, what is the minimum eating speed? ⌄

💡 Hint

There is no array to search — but the candidate speeds 1…max(piles) form an ordered range, and 'can she finish at speed k?' is monotonic. Binary search that boolean for its first true.

✅ Answer

4. At speed 4 the hours are ⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 ≤ 8 ✓. At speed 3 they are 1+2+3+4 = 10 > 8 ✗. This is 'binary search on the answer': O(N log M) where M is the largest pile — log M speeds tried, each verified with one O(N) sweep.

→ Solve on LeetCode ↗

H3 LeetCode 4 — Median of Two Sorted Arrays: find the median of [1, 3] and [2] in O(log(m+n)). ⌄

💡 Hint

Don't search for a value — search for a partition. Cut the smaller array at some index i, cut the larger at the complementary index j, and check whether every element left of the cut is ≤ every element right of it.

✅ Answer

2.0. Binary search the cut position in the shorter array only, which gives O(log(min(m, n))). A partition is correct when maxLeftA ≤ minRightB and maxLeftB ≤ minRightA; if it isn't, the comparison tells you which way to move the cut. For [1,2] and [3,4] the same method yields 2.5.

→ Solve on LeetCode ↗

In the Wild

Real-World Applications

🔀

Git

git bisect

Finding which commit introduced a bug across 1,000 commits takes about 10 builds instead of 1,000. Git checks out the middle commit, you mark it good or bad, and half the history is eliminated.

🔍 How it fits: The commit range is the sorted array and 'is the bug present?' is the monotonic predicate — false for every commit before the break, true for every one after. Binary search finds the flip point.

🗄️

Database Engines

B-Tree Index Descent

Every indexed lookup in Postgres or MySQL walks a B-tree, and each node is scanned with a binary search over its sorted keys. A table with a billion rows resolves in a handful of page reads.

🔍 How it fits: Keys within a node are sorted, so binary search picks the correct child pointer in O(log K) per node — the same halving logic, applied once per level of the tree.

📚

Standard Libraries

Insertion Points

Python's bisect module, Java's Arrays.binarySearch, and C++'s lower_bound / upper_bound are all boundary searches. Keeping a list sorted on insert is cheaper than re-sorting it.

🔍 How it fits: lower_bound is precisely the 'first occurrence' search from LeetCode 34, and upper_bound the 'last occurrence' variant. Java's binarySearch even returns -(insertionPoint) - 1 when the key is absent.

🎚️

Capacity Planning

Load Testing an Answer Space

Finding the highest request rate a service survives is not an array problem, yet teams binary search it: try 5,000 rps, it holds; try 10,000, it breaks; try 7,500. A dozen runs beat a linear ramp.

🔍 How it fits: Any monotonic pass/fail predicate over an ordered range of candidates is binary-searchable — the same shape as Koko Eating Bananas, applied to throughput, thread pools, or timeout budgets.

Quick Reference

Cheat Sheet

The Patterns

Start bounds (inclusive)

left = 0, right = n - 1

Loop

while (left <= right)

Midpoint (overflow-safe)

mid = left + (right - left) / 2

Too small / too big

left = mid + 1 / right = mid - 1

Boundary hit

answer = mid; keep shrinking

When to Use

✓ Searching a sorted array
✓ Finding an insertion point
✓ First or last occurrence of a value
✓ Nearest / floor / ceiling value
✓ Rotated or partially sorted arrays
✓ Peak finding in a bitonic array
✓ Minimising an answer under a constraint
✓ Any monotonic true/false predicate

Loop Invariants

Inclusive [left, right]

right = n - 1, loop on <=, move to mid ± 1.

Half-open [left, right)

right = n, loop on <, set right = mid (not mid - 1).

Never mix them

An inclusive bound with < skips the last element. A half-open bound with <= reads past the end.

Complexity

Time: O(log N) — the window halves every iteration

Space: O(1) iteratively, O(log N) recursively

Test Yourself

Quiz: Check Your Understanding

Question 1 of 9 Score: 0

Binary search runs in O(log N) time. What exactly is the "log N" counting? basic

Keep Learning

You've mastered Binary Search 🎉

This pattern powers git bisect, every database index, and half the "minimise X subject to Y" problems you'll meet — all from one halving loop.

Next, while the halving muscle is warm: LeetCode 278 — First Bad Version, then LeetCode 153 — Find Minimum in Rotated Sorted Array and LeetCode 162 — Find Peak Element.

Read the LeetCode 34 Case Study → ← Back to DSA Patterns