Binary Search

The Mental Model

Binary search is like playing “guess the number” optimally. Instead of guessing randomly, you always guess the middle. With each guess, you eliminate half the possibilities. This is why binary search is O(log n)—even with a billion elements, you need at most 30 guesses.

Pattern Recognition Signals:

“Minimum/Maximum value that satisfies condition”
“Find first/last occurrence”
Sorted array or monotonic property
Constraints allow O(log n) or O(n log n)

The Two Types of Binary Search

Type 1: Binary Search on Index

Find an element or position in a sorted array.

Type 2: Binary Search on Answer

The answer is a number in a range. Check if each candidate answer is valid. The validity forms a monotonic sequence (all NO, then all YES, or vice versa).

The Insight: Binary search works whenever you have a monotonic predicate—a condition that’s false for all values up to some point, then true for all values after (or vice versa).

Template: Binary Search on Index

Finding Exact Element

int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // Avoid overflow
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    
    return -1;  // Not found
}

Finding Lower Bound (First >= Target)

int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;  // Don't exclude mid, it might be the answer
        }
    }
    
    return lo;  // First position where arr[i] >= target
}

Finding Upper Bound (First > Target)

int upperBound(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (arr[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    return lo;  // First position where arr[i] > target
}

Template: Binary Search on Answer

This is the game-changer pattern. Many problems that seem impossible become easy with this technique.

// General template
bool canAchieve(int x) {
    // Return true if 'x' is achievable/valid
    // This function must be monotonic!
}

int binarySearchOnAnswer() {
    int lo = MIN_POSSIBLE_ANSWER;
    int hi = MAX_POSSIBLE_ANSWER;
    int answer = -1;
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (canAchieve(mid)) {
            answer = mid;       // mid is valid
            hi = mid - 1;       // Try to find smaller valid (for minimum)
            // lo = mid + 1;    // Try to find larger valid (for maximum)
        } else {
            lo = mid + 1;       // Need larger value
            // hi = mid - 1;    // Need smaller value (for maximum)
        }
    }
    
    return answer;
}

Classic Pattern: Minimum Maximum

Problem Type: “Minimize the maximum” or “Maximize the minimum” Example: Split array into K subarrays to minimize the maximum subarray sum. Approach: Binary search on the answer (the maximum sum). For each candidate, check if we can split into ≤ K subarrays.

bool canSplit(vector<int>& arr, int maxSum, int k) {
    int count = 1;
    int currentSum = 0;
    
    for (int x : arr) {
        if (x > maxSum) return false;  // Single element too large
        
        if (currentSum + x > maxSum) {
            count++;
            currentSum = x;
        } else {
            currentSum += x;
        }
    }
    
    return count <= k;
}

int splitArray(vector<int>& nums, int k) {
    int lo = *max_element(nums.begin(), nums.end());
    int hi = accumulate(nums.begin(), nums.end(), 0);
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (canSplit(nums, mid, k)) {
            hi = mid;  // Try smaller maximum
        } else {
            lo = mid + 1;
        }
    }
    
    return lo;
}

Codeforces Problems:

Problem	Rating	Link
Aggressive Cows (Classic)	1500	SPOJ
Magic Powder	1500	CF 670D2
Ropes	1200	CF 579B

Classic Pattern: Kth Element

Problem: Find the Kth smallest element in sorted matrix / merged sorted arrays. Approach: Binary search on the value. Count how many elements are ≤ mid.

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int lo = matrix[0][0];
    int hi = matrix[n-1][n-1];
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        // Count elements <= mid
        int count = 0;
        int col = n - 1;
        for (int row = 0; row < n; row++) {
            while (col >= 0 && matrix[row][col] > mid) {
                col--;
            }
            count += col + 1;
        }
        
        if (count < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    return lo;
}

Common Mistakes

Mistake 1: Wrong Loop Condition

// For exact search
while (lo <= hi)  // Use <= 

// For lower/upper bound
while (lo < hi)   // Use <

Mistake 2: Integer Overflow in Mid Calculation

// WRONG: Can overflow if lo + hi > INT_MAX
int mid = (lo + hi) / 2;

// CORRECT
int mid = lo + (hi - lo) / 2;

Mistake 3: Wrong Bounds Update When searching for minimum valid:

If canAchieve(mid) is true → hi = mid (not mid - 1)
If false → lo = mid + 1

When searching for maximum valid:

If canAchieve(mid) is true → lo = mid + 1
If false → hi = mid - 1

Mistake 4: Non-Monotonic Predicate Binary search only works if the predicate is monotonic. Always verify:

If canAchieve(x) is true, is canAchieve(x+1) also true? (or vice versa)

The Binary Search Decision Tree

Need to find something in sorted array?
├── Exact element → Standard binary search (lo <= hi)
├── First >= target → Lower bound
├── First > target → Upper bound
└── Last <= target → Upper bound - 1

Need to optimize (min/max) something?
├── Can you define canAchieve(x)?
│   ├── Is it monotonic? → Binary search on answer
│   └── Not monotonic → Different technique
└── No clear predicate → Not binary search

Advanced: Ternary Search

For unimodal functions (one peak/valley), use ternary search:

// Find maximum of unimodal function f
double ternarySearch(double lo, double hi) {
    for (int i = 0; i < 100; i++) {  // Precision iterations
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        
        if (f(m1) < f(m2)) {
            lo = m1;
        } else {
            hi = m2;
        }
    }
    
    return (lo + hi) / 2;
}

Practice Problems

Beginner (800-1200)

Problem	Pattern	Link
Binary Search	Basic	CSES
Interesting drink	Lower bound	CF 706B
Hamburgers	Binary search on answer	CF 371C

Intermediate (1200-1500)

Problem	Pattern	Link
Multiplication Table	BS on answer, counting	CF 448D
Ropes	BS on answer (real numbers)	CF 579B
Children’s Numbers	BS + greedy	CF 577B

Advanced (1500-1800)

Problem	Pattern	Link
Magic Powder	BS on answer	CF 670D2
Minimize the Maximum	Minimax BS	CF 1760E
Social Network	BS + data structures	CF 1234D

Key Takeaways

Monotonic Predicate

Binary search works when canAchieve(x) is monotonic (all false, then all true).

Search on Answer

When asked to minimize/maximize, binary search on the answer is often the key.

Bound Selection

Carefully choose lo and hi. lo = minimum possible, hi = maximum possible.

Off-by-One

Use lo < hi for bounds, lo <= hi for exact search. Be precise.

Next Up

Chapter 7: Sorting & Custom Comparators

Learn strategic sorting techniques and how custom comparators unlock powerful problem-solving approaches.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Binary Search

Binary Search

The Mental Model

The Two Types of Binary Search

Type 1: Binary Search on Index

Type 2: Binary Search on Answer

Template: Binary Search on Index

Finding Exact Element

Finding Lower Bound (First >= Target)

Finding Upper Bound (First > Target)

Template: Binary Search on Answer

Classic Pattern: Minimum Maximum

Classic Pattern: Kth Element

Common Mistakes

The Binary Search Decision Tree

Advanced: Ternary Search

Practice Problems

Beginner (800-1200)

Intermediate (1200-1500)

Advanced (1500-1800)

Key Takeaways

Monotonic Predicate

Search on Answer

Bound Selection

Off-by-One

Next Up

Chapter 7: Sorting & Custom Comparators

​Binary Search

​The Mental Model

​The Two Types of Binary Search

​Type 1: Binary Search on Index

​Type 2: Binary Search on Answer

​Template: Binary Search on Index

​Finding Exact Element

​Finding Lower Bound (First >= Target)

​Finding Upper Bound (First > Target)

​Template: Binary Search on Answer

​Classic Pattern: Minimum Maximum

​Classic Pattern: Kth Element

​Common Mistakes

​The Binary Search Decision Tree

​Advanced: Ternary Search

​Practice Problems

​Beginner (800-1200)

​Intermediate (1200-1500)

​Advanced (1500-1800)

​Key Takeaways

Monotonic Predicate

Search on Answer

Bound Selection

Off-by-One

​Next Up

Chapter 7: Sorting & Custom Comparators

Binary Search

The Mental Model

The Two Types of Binary Search

Type 1: Binary Search on Index

Type 2: Binary Search on Answer

Template: Binary Search on Index

Finding Exact Element

Finding Lower Bound (First >= Target)

Finding Upper Bound (First > Target)

Template: Binary Search on Answer

Classic Pattern: Minimum Maximum

Classic Pattern: Kth Element

Common Mistakes

The Binary Search Decision Tree

Advanced: Ternary Search

Practice Problems

Beginner (800-1200)

Intermediate (1200-1500)

Advanced (1500-1800)

Key Takeaways

Next Up