Binary Search Mastery

Binary search is deceptively simple: find an element in a sorted array in O(log n). Yet it's one of the most bug-prone algorithms - studies show that 90% of programmers cannot write a correct binary search on their first attempt. This article covers the classic algorithm, its variants, and advanced applications like "binary search on the answer" that appear frequently in interviews and production systems.

📋 At a Glance

Variant	Purpose	Returns
Classic	Find exact element	Index or -1
Lower bound	First element ≥ target	Insertion point
Upper bound	First element > target	Insertion point
Equal range	Range of equal elements	[lower, upper)
Binary search on answer	Find minimum/maximum satisfying condition	Optimal value

All variants: O(log n) time, O(1) space

🎯 What You'll Learn

After reading this article, you will be able to:

Write bug-free binary search every time using a systematic approach
Choose the right variant (lower bound, upper bound, equal range)
Apply binary search to non-array problems (parametric search)
Handle edge cases including duplicates, rotated arrays, and 2D matrices
Avoid classic bugs like integer overflow and off-by-one errors
Recognize binary search opportunities in interview problems

🔥 Production Story: The Midnight Pricing Bug

An e-commerce platform used binary search to find applicable price tiers based on order quantity. During a flash sale, customers reported being charged incorrect prices.

JAVA(27 lines)
Code
Loading syntax highlighter...

The bugs:

Order of 100 units returned tier 1 ($8) but should return tier 1 - correct by accident
Order of 99 units returned tier 1 ($8) instead of tier 0 ($10)!
Order of 500 units sometimes returned tier 1 instead of tier 2

Root cause: The code searched for exact match, but needed to find the last tier whose threshold ≤ quantity.

The fix:

JAVA(36 lines)
Code
Loading syntax highlighter...

The lesson: Binary search has many variants. Using exact-match search when you need bounds search causes subtle bugs that only manifest on boundary values.

🧠 Mental Model: The Binary Search Family

TEXT(44 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Classic Binary Search

🎮 Try It Yourself

Watch binary search divide the search space in half with each step. Enter a target value and observe how left, mid, and right pointers converge:

Binary Search
Time: O(log n)Space: O(1)
Target:
1 / 0
⚠️ Prerequisite:Array must be SORTED
✓ Use cases:Dictionary lookup, database indexes, finding boundaries, git bisect
🎯 Binary Search Invariant
target ∈ arr[left..right]
If target exists, it must be within current search bounds
Each iteration eliminates half of remaining elements → log₂(n) iterations max
Ready to search...
Pseudocode
1binarySearch(arr, target):
2  left = 0, right = n - 1
3  while left <= right:
4    mid = (left + right) / 2
5    if arr[mid] == target:
6      return mid  // Found!
7    elif arr[mid] < target:
8      left = mid + 1
9    else:
10      right = mid - 1
11  return -1  // Not found
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Search Space
Search Space
Eliminated
Eliminated
Mid
Mid
Found
Found
P · [ ] · R
Loading visualizer...

The Correct Implementation

JAVA(26 lines)
Code
Loading syntax highlighter...

Why `lo + (hi - lo) / 2`?

JAVA(15 lines)
Code
Loading syntax highlighter...

Loop Invariant Analysis

TEXT(29 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Lower Bound and Upper Bound

Lower Bound (bisect_left)

JAVA(26 lines)
Code
Loading syntax highlighter...

Upper Bound (bisect_right)

JAVA(26 lines)
Code
Loading syntax highlighter...

Equal Range

JAVA(27 lines)
Code
Loading syntax highlighter...

Comparison of Variants

Variant	Condition	When lo moves	When hi moves	Returns
Exact	arr[mid] == target	arr[mid] < target	arr[mid] > target	Found index or -1
Lower bound	arr[mid] >= target	arr[mid] < target	arr[mid] >= target	First ≥ target
Upper bound	arr[mid] > target	arr[mid] <= target	arr[mid] > target	First > target

🔬 Deep Dive: Binary Search on Answer

The Paradigm

Binary search isn't just for finding elements in arrays. It can solve any problem where:

The answer space is ordered (monotonic)
You can verify if a candidate answer is valid in reasonable time

TEXT(15 lines)
Code
Loading syntax highlighter...

Example: Minimum Ship Capacity

JAVA(49 lines)
Code
Loading syntax highlighter...

Example: Koko Eating Bananas

JAVA(32 lines)
Code
Loading syntax highlighter...

Example: Split Array Largest Sum

JAVA(42 lines)
Code
Loading syntax highlighter...

Recognizing Binary Search on Answer Problems

Pattern	Example Problem
"Minimize the maximum..."	Split array largest sum
"Maximize the minimum..."	Magnetic force between balls
"Find minimum X such that..."	Ship capacity, eating speed
"Find maximum X such that..."	Maximum candies allocated
Monotonic feasibility	If X works, X+1 also works (or vice versa)

🔬 Deep Dive: Rotated Sorted Array

Finding Element in Rotated Array

JAVA(37 lines)
Code
Loading syntax highlighter...

Finding Minimum in Rotated Array

JAVA(27 lines)
Code
Loading syntax highlighter...

Handling Duplicates

JAVA(42 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: 2D Matrix Search

Row-Column Sorted Matrix

JAVA(35 lines)
Code
Loading syntax highlighter...

Fully Sorted Matrix

JAVA(39 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Integer Overflow in Mid Calculation

JAVA(6 lines)
Code
Loading syntax highlighter...

Mistake 2: Wrong Loop Condition

JAVA(11 lines)
Code
Loading syntax highlighter...

Mistake 3: Off-by-One in Bound Updates

JAVA(11 lines)
Code
Loading syntax highlighter...

Mistake 4: Wrong Condition in Bounds Search

JAVA(9 lines)
Code
Loading syntax highlighter...

Mistake 5: Not Handling Empty Array

JAVA(12 lines)
Code
Loading syntax highlighter...

🐛 Debug This: The Buggy Binary Search Collection

These binary search implementations have bugs. Find and fix them:

JAVA(53 lines)
Code
Loading syntax highlighter...

💡 Hint

Look for:

Inclusive vs exclusive bounds consistency
Infinite loop conditions
Off-by-one errors in first occurrence
Integer overflow in multiplication
Returning lo vs lo-1

✅ Solution

JAVA(60 lines)
Code
Loading syntax highlighter...

Bugs explained:

search(): Using hi = length with while (lo < hi) but treating it as exact search. Also lo = mid causes infinite loop. Mixed paradigms.
firstOccurrence(): Using while (lo <= hi) with hi = mid causes infinite loop when lo == hi == mid and arr[mid] == target.
sqrt(): mid * mid overflows for large x. Also, the logic for finding floor(sqrt) was inverted.

💻 Exercises

Exercise 1: Find Peak Element ⭐

Find a peak element in array where arr[i] ≠ arr[i+1]. A peak is greater than neighbors.

JAVA(11 lines)
Code
Loading syntax highlighter...

💡 Hint

If arr[mid] < arr[mid+1], a peak must exist to the right. Otherwise, a peak exists to the left (or at mid).

Exercise 2: Search in 2D Matrix (Arbitrary Sorted) ⭐⭐

Matrix where rows are sorted left-to-right, columns are sorted top-to-bottom (but row end may be less than next row start).

JAVA(8 lines)
Code
Loading syntax highlighter...

Exercise 3: Find Minimum in Rotated Array II ⭐⭐⭐

Find minimum in rotated sorted array that may contain duplicates.

JAVA(8 lines)
Code
Loading syntax highlighter...

Exercise 4: Aggressive Cows (Binary Search on Answer) ⭐⭐⭐

Place C cows in N stalls at positions x₁, x₂, ..., xₙ. Maximize minimum distance between any two cows.

JAVA(10 lines)
Code
Loading syntax highlighter...

💡 Hint

Binary search on the answer (minimum distance). For each candidate distance D, check if you can place all cows with at least D distance apart using greedy placement.

Exercise 5: Median of Two Sorted Arrays ⭐⭐⭐⭐

Find median of two sorted arrays in O(log(min(m,n))) time.

JAVA(9 lines)
Code
Loading syntax highlighter...

💡 Hint

Binary search on partition point of smaller array. If we partition both arrays such that left halves have (m+n+1)/2 elements total, median is derived from elements around partition.

🎤 Interview Questions

Question 1: Why is binary search often implemented incorrectly?

Answer:

Binary search is tricky because of several interdependent decisions:

Bounds: inclusive vs exclusive?
- hi = arr.length - 1 (inclusive) vs hi = arr.length (exclusive)
- Must be consistent throughout
Loop condition: < or <=?
- while (lo < hi) for bounds search (hi = length)
- while (lo <= hi) for exact search (hi = length - 1)
Update rules: mid or mid±1?
- Must ensure progress (no infinite loops)
- Must not skip potential answers
Different variants need different logic
- Exact search, lower bound, upper bound all differ

The fix: Use templates. Memorize one correct implementation for each variant and always use it.

Question 2: When would you use binary search over hash table lookup?

Answer:

Use binary search when:

Memory constrained: Binary search is O(1) space, hash table is O(n)
Range queries needed: "Find all elements between A and B" - binary search gives O(log n + k), hash table is O(n)
Ordered iteration needed: Binary search maintains order, hash tables don't
Predecessor/successor queries: "Find largest element ≤ X" - O(log n) with binary search, O(n) with hash table
Data is already sorted: No preprocessing needed

Use hash table when:

Exact lookup only: O(1) average vs O(log n)
Frequent insertions/deletions: Hash table is O(1), maintaining sorted array is O(n)
Memory is plentiful: Hash table's O(1) lookup is hard to beat

Question 3: Explain binary search on answer with an example

Answer:

Binary search on answer finds optimal value when:

Answer space is ordered
There's a monotonic feasibility function

Example: Minimum pages allocation

Problem: N books with pages[i]. Allocate to K students such that maximum pages assigned to any student is minimized. Each student gets contiguous books.

JAVA(30 lines)
Code
Loading syntax highlighter...

The key insight: if we can allocate with max=X, we can also allocate with max=X+1. This monotonicity enables binary search.

Question 4: How would you handle duplicates in binary search?

Answer:

Duplicates affect what "find" means:

Find any occurrence: Standard binary search works (returns any matching index)
Find first occurrence (lower bound):

JAVA(5 lines)
Code
Loading syntax highlighter...

Find last occurrence:

JAVA(5 lines)
Code
Loading syntax highlighter...

Count occurrences: upperBound - lowerBound
Rotated array with duplicates: Worst case becomes O(n) because can't determine which half is sorted when arr[lo] == arr[mid] == arr[hi].

Question 5: Compare iterative vs recursive binary search

Answer:

Aspect	Iterative	Recursive
Space	O(1)	O(log n) stack
Performance	Slightly faster (no call overhead)	Slightly slower
Readability	More explicit	More elegant
Tail recursion	N/A	Could be optimized (not in Java)
Debugging	Easier (can inspect lo, hi)	Harder (stack frames)

Recommendation: Use iterative in production (O(1) space, no stack overflow risk). Use recursive when teaching or when algorithm naturally recursive.

JAVA(21 lines)
Code
Loading syntax highlighter...

📋 Quick Reference

Binary Search Templates

Template 1: Exact Search

JAVA(8 lines)
Code
Loading syntax highlighter...

Template 2: Lower Bound (First ≥ target)

JAVA(7 lines)
Code
Loading syntax highlighter...

Template 3: Upper Bound (First > target)

JAVA(7 lines)
Code
Loading syntax highlighter...

Template 4: Binary Search on Answer

JAVA(7 lines)
Code
Loading syntax highlighter...

Common Patterns

Pattern	Recognize By	Template
Find element	"Find X in sorted array"	Exact search
Find position	"Where would X be inserted?"	Lower/upper bound
Find first/last	"First occurrence of X"	Modified bounds
Find optimal	"Minimum capacity such that..."	Search on answer
Rotated array	"Sorted then rotated"	Two-phase analysis

Java Standard Library

JAVA(15 lines)
Code
Loading syntax highlighter...

📅 Review Schedule

Day	Focus	Time
Day 1	Read full article, understand all templates	60 min
Day 3	Implement exact, lower bound, upper bound from scratch	30 min
Day 7	Solve 3 "binary search on answer" problems	45 min
Day 14	Solve rotated array variants	30 min
Day 30	Mock interview: explain and implement	20 min

🔗 What's Next?

Part 9: Search in Specialized Structures covers:

Ternary search for unimodal functions
Interpolation search for uniform distributions
Exponential search for unbounded arrays
Fibonacci search
Jump search

Key insight preview: When data has known distribution or special properties, we can beat O(log n) with smarter search strategies.

This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Midnight Pricing Bug

🧠 Mental Model: The Binary Search Family

🔬 Deep Dive: Classic Binary Search

🎮 Try It Yourself

Binary Search

The Correct Implementation

Why lo + (hi - lo) / 2?

Loop Invariant Analysis

🔬 Deep Dive: Lower Bound and Upper Bound

Lower Bound (bisect_left)

Upper Bound (bisect_right)

Equal Range

Comparison of Variants

🔬 Deep Dive: Binary Search on Answer

The Paradigm

Example: Minimum Ship Capacity

Example: Koko Eating Bananas

Example: Split Array Largest Sum

Recognizing Binary Search on Answer Problems

🔬 Deep Dive: Rotated Sorted Array

Finding Element in Rotated Array

Finding Minimum in Rotated Array

Handling Duplicates

🔬 Deep Dive: 2D Matrix Search

Row-Column Sorted Matrix

Fully Sorted Matrix

⚠️ Common Mistakes

Mistake 1: Integer Overflow in Mid Calculation

Mistake 2: Wrong Loop Condition

Mistake 3: Off-by-One in Bound Updates

Mistake 4: Wrong Condition in Bounds Search

Mistake 5: Not Handling Empty Array

🐛 Debug This: The Buggy Binary Search Collection

💻 Exercises

Exercise 1: Find Peak Element ⭐

Exercise 2: Search in 2D Matrix (Arbitrary Sorted) ⭐⭐

Exercise 3: Find Minimum in Rotated Array II ⭐⭐⭐

Exercise 4: Aggressive Cows (Binary Search on Answer) ⭐⭐⭐

Exercise 5: Median of Two Sorted Arrays ⭐⭐⭐⭐

🎤 Interview Questions

Question 1: Why is binary search often implemented incorrectly?

Question 2: When would you use binary search over hash table lookup?

Question 3: Explain binary search on answer with an example

Question 4: How would you handle duplicates in binary search?

Question 5: Compare iterative vs recursive binary search

📋 Quick Reference

Binary Search Templates

Common Patterns

Java Standard Library

📅 Review Schedule

🔗 What's Next?

Tags:

Binary Search

Why `lo + (hi - lo) / 2`?