Binary Search Algorithm in 100 Seconds
Channel: Fireship
Full video link:
https://www.youtube.com/watch?v=MFhxShGxHWcAlgorithm • medium
Binary Search Complete Guide
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) |
Video Explainer
Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.
Binary Search Visualizer
Watch how low/high boundaries shrink while finding a target in a sorted array.
Binary Search VisualizerStep 1 / 2
Start with the full search range.
Array
[1, 3, 5, 7, 9, 11, 13, 15]
Target
11
Low / High / Mid
0 / 7 / 3 (value 7)
Decision
7 is too small, move low to mid + 1.
Core Concepts
Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.
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.
Putting It All Together
This walkthrough connects the core concepts of Binary Search into one end-to-end execution flow.
Step 1
Low/High bounds
Current active interval.
Before
Sorted
1358101418
- target = 14, low=0, high=6
→
After
Search range now
101418
- low=4, high=6
Transition
mid=3 (value 8)
→8 < 14 so low = mid + 1
Why this step matters: Low/High bounds is a required building block for understanding how Binary Search stays correct and performant on large inputs.
Step 2
Midpoint
Candidate index/value chosen each iteration.
Before
Range values
101418
- low=4, high=6
→
After
- Found at index 5
- Terminate immediately
Transition
mid=5 (value 14)
→value == target
Why this step matters: Midpoint is a required building block for understanding how Binary Search stays correct and performant on large inputs.
Step 3
Monotonic condition
Rule that decides left or right half.
Before
- Monotonic answer space
- Check condition at mid
→
After
- Tightened search interval
- Boundary converges to answer
Transition
Condition true -> move right bound
→Condition false -> move left bound
Why this step matters: Monotonic condition is a required building block for understanding how Binary Search stays correct and performant on large inputs.
Step 4
Boundary policy
Choose first true, last true, exact match, etc.
Before
- low <= high loop invariant
- Keep bounds inclusive
→
After
- Either found target or exhausted range
- Proof of correctness preserved
Transition
Update one bound each iteration
→Never discard potential answer
Why this step matters: Boundary policy is a required building block for understanding how Binary Search stays correct and performant on large inputs.
How It Compares
vs Linear scan
When to choose this: Choose binary search when sorted/monotonic structure exists.
Tradeoff: Requires setup conditions and careful boundary logic.
vs Hash lookup
When to choose this: Choose binary search when sorted order/range queries matter.
Tradeoff: Hash map is faster for exact-key average lookup.
vs Balanced tree
When to choose this: Choose binary search over arrays for read-heavy static datasets.
Tradeoff: Trees handle dynamic inserts/deletes better.
Real-World Stories and Company Examples
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.
Implementation Guide
Classic exact lookup over ascending sorted array.
Complexity: Time O(log n), Space O(1)
Binary search exact target
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
}
Common Problems and Failure Modes
- 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.
Tips and Tricks
- 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?
When to Use
Use these signals to decide if this data structure/algorithm is the right fit before implementation.
Real-system usage signals
- Drops search from
O(n)toO(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 (including 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.
LeetCode Progression (Easy to Hard)
Back to DSA Guide Catalog| # | 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) |