Om's Brain

4. Binary Search

20 min read

🔍 When Do You Reach For This?

You need to find the minimum (or maximum) value that satisfies some condition — and that condition is monotonic: once it flips from false → true, it stays true forever.

The search space doesn’t have to be an array. It can be a range of integers, a range of real numbers, anything — as long as monotonicity holds.

These problems typically ask:

  • Find the minimum value satisfying a constraint
  • Find the maximum value satisfying a constraint (flip the condition)
  • Kth smallest / Kth largest element
  • “Is it possible to achieve X with parameter ≤ Y?”

The Golden Rule

If condition(k) is true, then condition(k+1) is also true — binary search applies. The entire game is: design the condition function, set the bounds, copy the template.

💡 The Core Insight

Binary search isn’t just “find a value in a sorted array.” The real power:

Minimize k, such that condition(k) is True.

search space:  [lo ..................... hi]
condition:      F   F   F   F   T   T   T
                                ^
                              answer

After the loop exits, lo is the smallest value where condition flips to true.

What about "Maximize k such that condition(k) is True"?

Flip the condition. Find the minimum k where !condition(k) is true, then answer = k - 1. Or equivalently: find minimum k where condition(k) is false, answer = k - 1.

📋 The Universal Template

int binarySearch(/* params */) {
    auto condition = [&](int mid) -> bool {
        // design this per problem
    };
 
    int lo = MIN_VALUE, hi = MAX_VALUE;  // include ALL possible answers
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid))
            hi = mid;       // mid could be the answer, keep it
        else
            lo = mid + 1;   // mid is not valid, discard it
    }
    return lo;  // lo == hi == smallest k where condition is true
}

Three Things to Customize

DecisionRule
Bounds lo, hiInclude all possible answers. When in doubt, go wider.
Return valuelo = minimum valid. Need maximum? Return lo - 1 after flipping condition.
condition(mid)The hardest part. Must be monotonic (F F F ... T T T).

Why lo < hi and NOT lo <= hi?

With lo < hi, the loop exits when lo == hi — one element left, that’s the answer. With lo <= hi, you need extra logic to break and decide which to return. Error-prone.

Why lo + (hi - lo) / 2 and NOT (lo + hi) / 2?

Prevents integer overflow when lo + hi > INT_MAX.

🧩 Pattern 1 — Direct Search (The Basics)

The search space is an explicit sorted array. Condition is straightforward.

First Bad Version — LC 278 ⭐

Find minimum k such that isBadVersion(k) is true. Template fits perfectly.

// LC 278. First Bad Version
int firstBadVersion(int n) {
    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}
// TC - O(log n) | SC - O(1)

Sqrt(x) — LC 69 ⭐

Find minimum k such that k * k > x. Answer = k - 1.

// LC 69. Sqrt(x)
int mySqrt(int x) {
    long lo = 0, hi = (long)x + 1;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid > x)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo - 1;  // minimum k where k*k > x → answer is k-1
}
// TC - O(log x) | SC - O(1)

Search Insert Position — LC 35 ⭐

Find minimum k such that nums[k] >= target.

// LC 35. Search Insert Position
int searchInsert(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();   // hi = n because target might go at end
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}
// TC - O(log n) | SC - O(1)

Find First and Last Position — LC 34 🔥

Run template twice: once for first >= target, once for first > target.

// LC 34. Find First and Last Position of Element in Sorted Array
vector<int> searchRange(vector<int>& nums, int target) {
    int n = nums.size();
    if (n == 0) return {-1, -1};
 
    // first index where nums[mid] >= target
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    int left = lo;
    if (left == n || nums[left] != target) return {-1, -1};
 
    // first index where nums[mid] > target → last = that - 1
    lo = left, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) hi = mid;
        else lo = mid + 1;
    }
    return {left, lo - 1};
}
// TC - O(log n) | SC - O(1)

lower_bound / upper_bound in C++ STL

lower_bound(begin, end, target) → first element >= target upper_bound(begin, end, target) → first element > target These are exactly the two binary searches above. Use STL when allowed.

🧩 Pattern 2 — Binary Search on Answer (The Power Pattern)

This is where binary search gets interesting. The search space isn’t a given array — it’s a range of possible answers. You design a feasible(mid) function and binary search over the answer space.

When to spot this

Problem says “minimize the maximum” or “find the minimum X such that Y is possible.” You feel the urge to try DP or greedy, but the constraint has monotonicity: if capacity m works, then any capacity > m also works.

Capacity To Ship Packages Within D Days — LC 1011 🔥

Find minimum capacity such that all packages ship within D days.

  • If capacity m works → any capacity > m also works. ✓ Monotonic.
  • lo = max(weights) (must carry heaviest single package)
  • hi = sum(weights) (ship everything in 1 day)
// LC 1011. Capacity To Ship Packages Within D Days
int shipWithinDays(vector<int>& weights, int days) {
    auto feasible = [&](int cap) -> bool {
        int d = 1, total = 0;
        for (int w : weights) {
            total += w;
            if (total > cap) {
                total = w;
                if (++d > days) return false;
            }
        }
        return true;
    };
 
    int lo = *max_element(weights.begin(), weights.end());
    int hi = accumulate(weights.begin(), weights.end(), 0);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log S) where S = sum(weights) | SC - O(1)

Split Array Largest Sum — LC 410 🔥

Minimize the largest subarray sum when splitting into m parts. Structurally identical to LC 1011.

// LC 410. Split Array Largest Sum
int splitArray(vector<int>& nums, int k) {
    auto feasible = [&](int threshold) -> bool {
        int count = 1, total = 0;
        for (int x : nums) {
            total += x;
            if (total > threshold) {
                total = x;
                if (++count > k) return false;
            }
        }
        return true;
    };
 
    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 (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log S) | SC - O(1)

"But is the answer actually a real subarray sum?"

Yes — proof by contradiction. If lo is not a real subarray sum, then every subarray sum < lo. That means feasible(lo - 1) is also true, contradicting lo being the minimum. ∎

Koko Eating Bananas — LC 875 🔥

Minimum eating speed to finish within H hours.

// LC 875. Koko Eating Bananas
int minEatingSpeed(vector<int>& piles, int h) {
    auto feasible = [&](int speed) -> bool {
        long hours = 0;
        for (int p : piles)
            hours += (p + speed - 1) / speed;   // ceil division
        return hours <= h;
    };
 
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log M) where M = max(piles) | SC - O(1)

Minimum Days to Make m Bouquets — LC 1482 🔥

If we can make m bouquets after d days, we can after d+1 too. Monotonic. ✓

// LC 1482. Minimum Number of Days to Make m Bouquets
int minDays(vector<int>& bloomDay, int m, int k) {
    if ((long)m * k > bloomDay.size()) return -1;
 
    auto feasible = [&](int day) -> bool {
        int bouquets = 0, flowers = 0;
        for (int b : bloomDay) {
            if (b <= day) {
                if (++flowers == k) { bouquets++; flowers = 0; }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    };
 
    int lo = *min_element(bloomDay.begin(), bloomDay.end());
    int hi = *max_element(bloomDay.begin(), bloomDay.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log D) where D = max(bloomDay) | SC - O(1)

Smallest Divisor Given a Threshold — LC 1283 ⭐

// LC 1283. Find the Smallest Divisor Given a Threshold
int smallestDivisor(vector<int>& nums, int threshold) {
    auto condition = [&](int d) -> bool {
        int sum = 0;
        for (int x : nums) sum += (x + d - 1) / d;
        return sum <= threshold;
    };
 
    int lo = 1, hi = *max_element(nums.begin(), nums.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log M) | SC - O(1)

Template cheatsheet for "Binary Search on Answer" 

1. Identify what you're minimizing (capacity, speed, days, divisor...)
2. lo = smallest possible answer, hi = largest possible answer
3. Write feasible(mid): can we achieve the goal with this value?
4. Copy-paste the template. Done.

🧩 Pattern 3 — Kth Smallest (Binary Search + Counting)

Instead of sorting/heap, binary search on the value and count how many elements are ≤ mid.

When to spot this

Kth smallest in a virtual collection (multiplication table, pair distances, ugly numbers) where you can’t enumerate all elements but can count elements ≤ a given value.

Kth Smallest in Multiplication Table — LC 668 💀

Row i has multiples of i. Count of values ≤ num in row i = min(num / i, n).

// LC 668. Kth Smallest Number in Multiplication Table
int findKthNumber(int m, int n, int k) {
    auto enough = [&](int num) -> bool {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            int add = min(num / i, n);
            if (add == 0) break;    // early exit
            count += add;
        }
        return count >= k;
    };
 
    int lo = 1, hi = m * n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(m log(mn)) | SC - O(1)

Kth Smallest Pair Distance — LC 719 💀

Sort array. For a given dist, count pairs with distance ≤ dist using two pointers.

// LC 719. Find K-th Smallest Pair Distance
int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
 
    auto enough = [&](int dist) -> bool {
        int count = 0, j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && nums[j] - nums[i] <= dist) j++;
            count += j - i - 1;
        }
        return count >= k;
    };
 
    int lo = 0, hi = nums.back() - nums.front();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(n log n + n log W) where W = max - min | SC - O(1)

Ugly Number III — LC 1201 📍

Count ugly numbers ≤ num using inclusion-exclusion with LCM.

// LC 1201. Ugly Number III
int nthUglyNumber(int n, int a, int b, int c) {
    long ab = lcm((long)a, b);
    long ac = lcm((long)a, c);
    long bc = lcm((long)b, c);
    long abc = lcm(ab, c);
 
    auto enough = [&](long num) -> bool {
        long cnt = num/a + num/b + num/c - num/ab - num/ac - num/bc + num/abc;
        return cnt >= n;
    };
 
    long lo = 1, hi = 2e9;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (enough(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// TC - O(log(2e9)) | SC - O(1)

🧩 Pattern 4 — Tricky Conditions (Rotated / Peak / Non-obvious)

The search space is a modified sorted array. The condition for shrinking isn’t straightforward — you need to reason about which half to keep.

Find Peak Element — LC 162 🔥

A peak exists if the array isn’t purely decreasing. Compare mid with mid + 1:

  • If nums[mid] < nums[mid + 1] → peak is to the right
  • Else → peak is at mid or to the left
// LC 162. Find Peak Element
int findPeakElement(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1])
            lo = mid + 1;   // peak is right of mid
        else
            hi = mid;       // mid could be peak
    }
    return lo;
}
// TC - O(log n) | SC - O(1)

Why this works

We always move towards a strictly increasing direction. Since nums[-1] = nums[n] = -∞, we’re guaranteed to converge on a peak.

Find Minimum in Rotated Sorted Array — LC 153 🔥

Compare mid with hi. If nums[mid] > nums[hi] → min is in right half.

// LC 153. Find Minimum in Rotated Sorted Array
int findMin(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi])
            lo = mid + 1;   // min is right of mid
        else
            hi = mid;       // mid could be the min
    }
    return nums[lo];
}
// TC - O(log n) | SC - O(1)

Search in Rotated Sorted Array — LC 33 🔥

One half is always sorted. Figure out which, then check if target lies in that sorted half.

// LC 33. Search in Rotated Sorted Array
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
 
        if (nums[lo] <= nums[mid]) {              // left half sorted
            if (nums[lo] <= target && target < nums[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        } else {                                    // right half sorted
            if (nums[mid] < target && target <= nums[hi])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
    }
    return -1;
}
// TC - O(log n) | SC - O(1)

This problem uses lo <= hi

Because we need an exact match and might return mid directly. This is one of the few cases where lo <= hi is cleaner than lo < hi.

Search in Rotated Sorted Array II (with duplicates) — LC 81 📍

Same as above, but when nums[lo] == nums[mid] == nums[hi], we can’t decide which half is sorted. Shrink both ends.

// LC 81. Search in Rotated Sorted Array II
bool search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return true;
 
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
            lo++; hi--;                            // can't determine, shrink
        } else if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
    }
    return false;
}
// TC - O(log n) avg, O(n) worst | SC - O(1)

🧩 Pattern 5 — Binary Search on Two Arrays

The search space spans across two sorted arrays. You partition both arrays such that left halves and right halves satisfy a condition.

Median of Two Sorted Arrays — LC 4 💀

Binary search on the shorter array. Partition both arrays into left/right halves of equal total size. Valid partition: maxLeft1 <= minRight2 and maxLeft2 <= minRight1.

// LC 4. Median of Two Sorted Arrays
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) swap(nums1, nums2);
    int n = nums1.size(), m = nums2.size();
    int half = (n + m + 1) / 2;
 
    int lo = 0, hi = n;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;   // partition in nums1
        int j = half - i;             // partition in nums2
 
        int left1  = (i > 0) ? nums1[i - 1] : INT_MIN;
        int right1 = (i < n) ? nums1[i]     : INT_MAX;
        int left2  = (j > 0) ? nums2[j - 1] : INT_MIN;
        int right2 = (j < m) ? nums2[j]     : INT_MAX;
 
        if (left1 <= right2 && left2 <= right1) {
            if ((n + m) % 2 == 1)
                return max(left1, left2);
            return (max(left1, left2) + min(right1, right2)) / 2.0;
        }
        if (left1 > right2)
            hi = i - 1;
        else
            lo = i + 1;
    }
    return -1;  // unreachable
}
// TC - O(log min(n,m)) | SC - O(1)

🧩 Pattern 6 — Binary Search on Matrix

Search a 2D Matrix — LC 74 ⭐

Rows are sorted, first element of each row > last of previous. Treat as a flat sorted array.

// LC 74. Search a 2D Matrix
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}
// TC - O(log(mn)) | SC - O(1)

Search a 2D Matrix II — LC 240 🔥

Each row sorted, each column sorted, but no global ordering. Start from top-right corner.

// LC 240. Search a 2D Matrix II
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int r = 0, c = matrix[0].size() - 1;
    while (r < matrix.size() && c >= 0) {
        if (matrix[r][c] == target) return true;
        if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
}
// TC - O(m + n) | SC - O(1)

This isn't classical binary search

It’s a “staircase search” — but it’s the standard approach for this matrix type and frequently paired with binary search problems.

🧩 Pattern 7 — C++ STL: lower_bound / upper_bound

When the problem gives you a sorted structure and asks for lookups, leverage STL.

Time Based Key-Value Store — LC 981 🔥

// LC 981. Time Based Key-Value Store
class TimeMap {
    unordered_map<string, map<int, string>> store;
public:
    void set(string key, string value, int timestamp) {
        store[key][timestamp] = value;
    }
    string get(string key, int timestamp) {
        auto& m = store[key];
        auto it = m.upper_bound(timestamp);   // first entry > timestamp
        if (it == m.begin()) return "";
        return prev(it)->second;              // largest entry <= timestamp
    }
};
// set: O(log n) | get: O(log n) | SC - O(n)

Random Pick with Weight — LC 528 📍

Build prefix sum of weights. Pick random number in [1, total]. Binary search for the bucket.

// LC 528. Random Pick with Weight
class Solution {
    vector<int> psum;
public:
    Solution(vector<int>& w) {
        psum.resize(w.size());
        partial_sum(w.begin(), w.end(), psum.begin());
    }
    int pickIndex() {
        int target = rand() % psum.back() + 1;
        return lower_bound(psum.begin(), psum.end(), target) - psum.begin();
    }
};
// init: O(n) | pick: O(log n)

🧠 Master Cheatsheet

Pattern Recognition

Signal in problemPattern to use
”Find minimum X such that Y is possible”Binary Search on Answer
Minimize the maximum / maximize the minimumBinary Search on Answer
Kth smallest in virtual collectionBS + Counting
Sorted array, find target / boundaryDirect BS
Rotated sorted arrayTricky Condition BS
Peak / valley in arrayCompare mid with neighbor
Two sorted arrays, find median / kthPartition BS
Sorted matrix searchFlatten or staircase

Template Quick Reference

MINIMIZE k such that condition(k) is TRUE:
    lo, hi = bounds covering all answers
    while (lo < hi):
        mid = lo + (hi - lo) / 2
        if condition(mid): hi = mid
        else: lo = mid + 1
    return lo

MAXIMIZE k such that condition(k) is TRUE:
    → Find min k where condition is FALSE, return k - 1
    → Or flip: lo = mid when condition true, hi = mid - 1 when false
      (use upper mid: mid = lo + (hi - lo + 1) / 2 to avoid infinite loop)

Common Bounds

Capacity / Split problems:  lo = max(arr),  hi = sum(arr)
Speed / Rate problems:      lo = 1,         hi = max(arr)
Day / Time problems:        lo = min(arr),  hi = max(arr)
Kth smallest:               lo = min_val,   hi = max_val

The feasible Function Patterns

Greedy simulation:  iterate array, greedily pack/consume, count segments/days/hours
Counting:           for each row/group, count elements ≤ mid
Math:               inclusion-exclusion, LCM/GCD for divisibility counting
Two pointers:       sort + count pairs within distance

Avoid Infinite Loops

Rule: every iteration must shrink the search space by at least 1.

Using "lo < hi" with:
  hi = mid, lo = mid + 1  → use lower mid (default)    ✓ always safe
  lo = mid, hi = mid - 1  → use UPPER mid (+ 1 in calc) ✓ prevents stuck

When 2 elements left [lo, hi]:
  lower mid = lo  → "lo = mid" doesn't shrink → infinite loop!  Use upper mid.
  upper mid = hi  → "hi = mid" doesn't shrink → infinite loop!  Use lower mid.

lower_bound(begin, end, val)  →  first element >= val
upper_bound(begin, end, val)  →  first element >  val
 
// "last element <= val":
auto it = upper_bound(begin, end, val);
if (it != begin) --it;   // now *it <= val

1 item under this folder.

Mindmap

Graph View