Binary Search Complete Guide

Algorithm • medium

Binary search repeatedly halves a sorted search space, making it one of the highest-impact logarithmic-time techniques.

It applies beyond arrays: any monotonic predicate can often be solved with binary search on answer space.

The hard part is boundary correctness, not the core idea.

Typical Complexity Baseline

Metric	Value
Search	`O(log n)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Binary search halve the range

Each comparison kills off half of the remaining candidates, giving log₂(n) work.

Step 1/6Initial range [0, 15]. Target = 29.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Binary Search Algorithm in 100 Seconds

Channel: Fireship

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Low/High bounds

What it is Current active interval.

Why it matters Low/High bounds is a required building block for understanding how Binary Search stays correct and performant on large inputs.

Midpoint

What it is Candidate index/value chosen each iteration.

Why it matters Midpoint is a required building block for understanding how Binary Search stays correct and performant on large inputs.

Monotonic condition

What it is Rule that decides left or right half.

Why it matters Monotonic condition is a required building block for understanding how Binary Search stays correct and performant on large inputs.

Boundary policy

What it is Choose first true, last true, exact match, etc.

Why it matters Boundary policy is a required building block for understanding how Binary Search stays correct and performant on large inputs.

Termination condition

What it is Loop invariant proving progress each step.

Why it matters Termination condition is a required building block for understanding how Binary Search stays correct and performant on large inputs.

Monotonic

What it is Condition changes in one direction only over domain.

Why it matters Condition changes in one direction only over domain. In Binary Search, this definition helps you reason about correctness and complexity when inputs scale.

Lower bound

What it is First index where condition becomes true.

Why it matters First index where condition becomes true. In Binary Search, this definition helps you reason about correctness and complexity when inputs scale.

Upper bound

What it is First index greater than target.

Why it matters First index greater than target. In Binary Search, this definition helps you reason about correctness and complexity when inputs scale.

Search on answer

What it is Binary search over value range instead of array index.

Why it matters Binary search over value range instead of array index. In Binary Search, this definition helps you reason about correctness and complexity when inputs scale.

Invariant

What it is Property that remains true across loop iterations.

Why it matters Property that remains true across loop iterations. In Binary Search, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/6

Initial range [0, 15]. Target = 29.

Step 2/6

mid = (0+15)/2 = 7. arr[7] = 23. 23 < 29 → discard left half.

Step 3/6

New range [8, 15].

Step 4/6

mid = (8+15)/2 = 11. arr[11] = 35. 35 > 29 → discard right half.

Step 5/6

New range [8, 10].

Step 6/6

mid = (8+10)/2 = 9. arr[9] = 29 → found at index 9.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Linear scan

Choose this when Choose binary search when sorted/monotonic structure exists.

Tradeoff Requires setup conditions and careful boundary logic.

vs. Hash lookup

Choose this when Choose binary search when sorted order/range queries matter.

Tradeoff Hash map is faster for exact-key average lookup.

vs. Balanced tree

Choose this when Choose binary search over arrays for read-heavy static datasets.

Tradeoff Trees handle dynamic inserts/deletes better.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Google

Search infrastructure uses binary-search-style lookups across sorted index segments and posting lists.

Takeaway Logarithmic probing remains core at web scale.

Netflix

Capacity and quality threshold tuning often applies binary search on monotonic metrics.

Takeaway Binary search helps optimize parameters quickly.

Databases

B-tree pages and sorted blocks rely on binary search to locate keys in each node/page.

Takeaway Storage engines depend on reliable boundary-search behavior.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Classic exact lookup over ascending sorted array.

Complexity: Time O(log n), Space O(1)

Binary search exact target

Language

function binarySearch(values: number[], target: number): number {
  let lowIndex = 0
  let highIndex = values.length - 1

  while (lowIndex <= highIndex) {
    const midIndex = lowIndex + Math.floor((highIndex - lowIndex) / 2)
    const midValue = values[midIndex]

    if (midValue === target) return midIndex
    if (midValue < target) lowIndex = midIndex + 1
    else highIndex = midIndex - 1
  }

  return -1
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Incorrect loop condition causing infinite loops.
Midpoint overflow in languages using fixed-size integers.
Mixing inclusive and exclusive bounds.
Returning wrong boundary variant for first/last occurrence tasks.
Applying binary search without verifying monotonicity.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Binary search works on monotonic conditions, not only sorted arrays.
Choose one boundary style (first true / last true / exact) and stay consistent.
Use while-low<=high or while-low<high intentionally; mixing both causes bugs.
Keep invariant comments near loop: what region is still possible?

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Drops search from O(n) to O(log n) when monotonic order exists.
Works for index lookup and optimization (minimum/maximum feasible value).
Predictable performance at very large input sizes.

LeetCode-specific tips (pattern-identification signals)

Identification signal: search space is sorted or monotonic, so you can discard half each decision.
Identification signal: prompt asks for first/last valid position, minimum feasible value, or boundary condition.
If brute force checks every value but condition is monotone true/false, switch to binary search on answer.
For Binary Search questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Binary Search	Easy	`O(log n)`
2	Search Insert Position	Easy	`O(log n)`
3	First Bad Version	Easy	`O(log n)`
4	Find First and Last Position	Medium	`O(log n)`
5	Search in Rotated Sorted Array	Medium	`O(log n)`
6	Find Peak Element	Medium	`O(log n)`
7	Koko Eating Bananas	Medium	`O(n log m)`
8	Median of Two Sorted Arrays	Hard	`O(log(min(m,n)))`
9	Split Array Largest Sum	Hard	`O(n log m)`
10	Find in Mountain Array	Hard	`O(log n)`