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 Golden Rule

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

Interview Strategy

Always give the O(n) brute-force / linear scan first, then optimize to O(log n) binary search.

📋 The Universal Template

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

int binarySearch(/* params */) {
    int s = MIN_VALUE, e = MAX_VALUE;
    int res = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (isValid(mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
DecisionRule
Bounds s, eInclude all possible answers.
isValid(mid)Must be monotonic (F F F ... T T T).
DirectionMinimizing → save & go left. e = mid - 1
Maximizing → save & go right. s = mid + 1

Stop Condition

Loop exits when s and e cross. s points to the first valid answer.

                   e   s
isValid:   F   F   F | T   T   T
                   ↑
             they cross
 
Result:
s = first valid = res

🧩 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
// f f f t t
int firstBadVersion(int n) {
    int s = 1, e = n, res = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (isBadVersion(mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// TC - O(log n) | SC - O(1)

Sqrt(x) — LC 69 ⭐

Find the largest k such that k * k <= x. Maximize → save & go right.

// LC 69. Sqrt(x)
int mySqrt(int x) {
    int s = 0, e = x, res = 0;
    while (s <= e) {
        long mid = s + (e - s) / 2;
        if (mid * mid <= x) {
            res = mid;       // mid works, try bigger
            s = mid + 1;
        } else {
            e = mid - 1;
        }
    }
    return res;
}
// TC - O(log x) | SC - O(1)

Search Insert Position — LC 35 ⚠️ 📍

Find minimum index where nums[mid] >= target. If target is found, return it directly.

// LC 35. Search Insert Position
int searchInsert(vector<int>& nums, int t) {
    int s = 0, e = nums.size() - 1, ans = nums.size();
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (nums[mid] == t) return mid;
        if (nums[mid] > t) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return ans;
}
// TC - O(log n) | SC - O(1)

Find First and Last Position — LC 34 ⭐

Run template twice: first occurrence → save & go left. Last occurrence → save & go right.

// 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 occurrence: when found, save & go left
    int s = 0, e = n - 1, first = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (nums[mid] == target) { first = mid; e = mid - 1; }
        else if (nums[mid] < target) s = mid + 1;
        else e = mid - 1;
    }
    if (first == -1) return {-1, -1};
 
    // last occurrence: when found, save & go right
    s = first, e = n - 1;
    int last = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (nums[mid] == target) { last = mid; s = mid + 1; }
        else if (nums[mid] < target) s = mid + 1;
        else e = mid - 1;
    }
    return {first, last};
}
// 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 do the same thing internally. 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 an isValid(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.
  • s = max(weights) (must carry heaviest single package)
  • e = sum(weights) (ship everything in 1 day)
// LC 1011. Capacity To Ship Packages Within D Days
bool isValid(vector<int>& weights, int days, int mid) {
    int d = 1, sum = 0;
    for (auto i : weights) {
        sum += i;
        if (sum > mid) {
            d++;
            sum = i;
            if (d > days) return false;
        }
    }
    return true;
}
 
int shipWithinDays(vector<int>& weights, int days) {
    int s = *max_element(weights.begin(), weights.end());
    int e = 0; for (auto i : weights) e += i;
    int res = -1;
 
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (isValid(weights, days, mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// TC - O(n log S) where S = sum(weights) | SC - O(1)

Split Array Largest Sum — LC 410 💀 📍

If we can split the array with largest sum ≤ S, we can with S+1 too. Monotonic. ✓

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

// LC 410. Split Array Largest Sum
bool isValid(vector<int>& nums, int k, int threshold) {
    int count = 1, total = 0;
    for (int x : nums) {
        total += x;
        if (total > threshold) {
            count++;
            total = x;
            if (count > k) return false;
        }
    }
    return true;
}
 
int splitArray(vector<int>& nums, int k) {
    int s = *max_element(nums.begin(), nums.end());
    int e = accumulate(nums.begin(), nums.end(), 0);
    int res = -1;
 
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (isValid(nums, k, mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// TC - O(n log S) | SC - O(1)

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

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

Koko Eating Bananas — LC 875 ⭐

If Koko can finish all bananas at speed k, she can at k+1 too. Monotonic. ✓

Minimum eating speed to finish within H hours.

// LC 875. Koko Eating Bananas
bool canEat(vector<int>& piles, int h, int speed) {
    long long hours = 0;
    for (auto& p : piles) {
        hours += ceil((double)p / speed);
    }
    return hours <= h;
}
 
int minEatingSpeed(vector<int>& piles, int h) {
    int s = 1, e = *max_element(piles.begin(), piles.end());
    int ans = -1;
 
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (canEat(piles, h, mid)) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return ans;
}
// 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
bool canMakeBouquets(vector<int>& bloomDay, int m, int k, int days) {
    int adjacentCnt = 0, noOfBouquets = 0;
    for (auto& i : bloomDay) {
        if (i <= days) {           // this flower has bloomed
            adjacentCnt++;
            if (adjacentCnt == k) {
                noOfBouquets++;
                adjacentCnt = 0;   // used these flowers, reset
            }
        } else {
            adjacentCnt = 0;       // streak broken
        }
    }
    return noOfBouquets >= m;
}
 
int minDays(vector<int>& bloomDay, int m, int k) {
    if ((long)m * k > bloomDay.size()) return -1;
 
    int s = *min_element(bloomDay.begin(), bloomDay.end());
    int e = *max_element(bloomDay.begin(), bloomDay.end());
    int res = -1;
 
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (canMakeBouquets(bloomDay, m, k, mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// 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
bool isValid(vector<int>& nums, int threshold, int divisor) {
    int sum = 0;
    for (auto& x : nums) 
	    sum += ceil( (double)x / divisor );
    return sum <= threshold;
}
 
int smallestDivisor(vector<int>& nums, int threshold) {
    int s = 1, e = *max_element(nums.begin(), nums.end());
    int res = -1;
 
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (isValid(nums, threshold, mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// 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. s = smallest possible answer, e = largest possible answer
3. Write isValid(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
bool enough(int m, int n, int k, int num) {
    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 findKthNumber(int m, int n, int k) {
    int s = 1, e = m * n, res = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (enough(m, n, k, mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// 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 s = 0, e = nums.back() - nums.front(), res = -1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (enough(mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// 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 s = 1, e = 2e9, res = -1;
    while (s <= e) {
        long mid = s + (e - s) / 2;
        if (enough(mid)) {
            res = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return res;
}
// 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
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
 
        if (n == 1) return 0;
        if (nums[0] > nums[1]) return 0;
        if (nums[n - 1] > nums[n - 2]) return n - 1;
 
        int s = 1, e = n - 2;
 
        while (s <= e) {
            int mid = s + (e - s) / 2;
 
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) return mid;
            else if (nums[mid] > nums[mid - 1]) s = mid + 1;
            else e = mid - 1;
        }
 
        return -1;
    }
};
// 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.

Peak/Min problems use s < e instead of s <= e

Because we’re not looking for an exact match — we’re converging on a position. s <= e with e = mid would infinite loop when s == e == mid.

Find Minimum in Rotated Sorted Array — LC 153 🔥

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

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

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

Same as above, but when nums[s] == nums[mid] == nums[e], 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 s = 0, e = nums.size() - 1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (nums[mid] == target) return true;
        if (nums[s] == nums[mid] && nums[mid] == nums[e]) {
            s++; e--; // for edge case element repeated
            continue;
        }
 
        if (nums[s] <= nums[mid]) { // left half sorted
            if (nums[s] <= target && target < nums[mid])
                e = mid - 1;
            else
                s = mid + 1;
        } else {                   // right half sorted
            if (nums[mid] < target && target <= nums[e])
                s = mid + 1;
            else
                e = 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 s = 0, e = n;
    while (s <= e) {
        int i = s + (e - s) / 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)
            e = i - 1;
        else
            s = 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 s = 0, e = m * n - 1;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        if (val < target) s = mid + 1;
        else e = 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 isValid(k) is TRUE:
    s, e = bounds covering all answers
    res = -1
    while (s <= e):
        mid = s + (e - s) / 2
        if isValid(mid): res = mid, e = mid - 1   // save & go left
        else: s = mid + 1
    return res

MAXIMIZE k such that isValid(k) is TRUE:
    s, e = bounds covering all answers
    res = -1
    while (s <= e):
        mid = s + (e - s) / 2
        if isValid(mid): res = mid, s = mid + 1   // save & go right
        else: e = mid - 1
    return res

Common Bounds

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

The isValid 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

When to use s < e vs s <= e

s <= e  →  default for most problems (exact match, minimize/maximize with res)
s < e   →  convergence problems (peak, min in rotated) where you do e = mid (not mid-1)
           because mid itself might be the answer and you can't skip it

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