C++ In Practice - Binary Search Variants

Binary Search Variants (C++11 Deep Dive)

In C++, you should almost never write a raw while (left <= right) loop for standard searches. The STL provides rigorous, optimized, and bug-free implementations in <algorithm>.

STL Binary Search Tools

1. std::binary_search(begin, end, val): Returns bool (exists or not).
2. std::lower_bound(begin, end, val): Returns iterator to first element >= val.
3. std::upper_bound(begin, end, val): Returns iterator to first element > val.
4. std::equal_range(begin, end, val): Returns pair of {lower_bound, upper_bound}.

Deep Dive: lower_bound vs upper_bound

• Lower Bound: Finds the start of a range of identical values.
• Upper Bound: Finds the end (technically, the element after the end) of a range.
• Count elements: upper_bound - lower_bound.

---

1. First and Last Occurrence (The STL Way)

Problem: Find starting and ending position of target.

Complexity: Time O(\log N) | Space O(1).

#include <vector>
#include <algorithm>

std::vector<int> searchRange(std::vector<int>& nums, int target) {
    // 1. Find first occurrence (lower_bound)
    auto lb = std::lower_bound(nums.begin(), nums.end(), target);
    
    // Check if target was actually found
    if (lb == nums.end() || *lb != target) {
        return {-1, -1};
    }
    
    // 2. Find upper bound (first element > target)
    auto ub = std::upper_bound(nums.begin(), nums.end(), target);
    
    // Calculate indices
    // ub points to the element AFTER the last target, so decrement index by 1
    return {(int)(lb - nums.begin()), (int)(ub - nums.begin() - 1)};
}

---

2. Search in Rotated Sorted Array

Problem: Find target in [4,5,6,7,0,1,2].

Logic: One half is always sorted. Determine which half, then check if target lies within that range.

Pitfall: Calculating mid using (left + right) / 2 causes integer overflow when left + right > INT_MAX.

Correct C++: mid = left + (right - left) / 2.

#include <vector>

int searchRotated(std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        // Check if Left Half is sorted
        if (nums[left] <= nums[mid]) {
            // Target is in the left sorted range
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } 
        // Otherwise, Right Half must be sorted
        else {
            // Target is in the right sorted range
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

---

3. Search a 2D Matrix (Mapping 1D to 2D)

Problem: Matrix sorted row-wise and column-wise (or strictly increasing).

Strictly Increasing: Treat as 1D array.

Mapping: 1D index i -> matrix[i / cols][i % cols].

#include <vector>

bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
    if (matrix.empty()) return false;
    int m = matrix.size();
    int n = matrix[0].size();
    
    int left = 0;
    int right = m * n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        int val = matrix[row][col];

        if (val == target) return true;
        if (val < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

---

4. Find Peak Element

Problem: Find index i where nums[i-1] < nums[i] > nums[i+1].

Pattern: Binary Search on Unsorted Array (Hill Climbing).

Invariant: If nums[mid] < nums[mid+1], we are on an upward slope. The peak must be to the right (or it is mid+1).

#include <vector>

int findPeakElement(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[mid + 1]) {
            // We are on a downward slope. Peak is mid or to the left.
            right = mid; 
        } else {
            // We are on an upward slope. Peak is strictly to the right.
            left = mid + 1;
        }
    }
    // Loop terminates when left == right
    return left;
}

---

5. Binary Search on Answer: Koko Eating Bananas

Problem: Find min integer k such that condition holds.

Pattern: The condition canFinish(k) is monotonic. False, False, ... True, True. Find the first True.

Integer Math: ceil(pile / k) can be written as (pile + k - 1) / k using integer division to avoid double precision issues.

#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
public:
    int minEatingSpeed(std::vector<int>& piles, int h) {
        // Range of possible speeds: 1 to Max Pile Size
        int left = 1;
        int right = *std::max_element(piles.begin(), piles.end());

        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (canFinish(piles, h, mid)) {
                right = mid; // Try smaller speed
            } else {
                left = mid + 1; // Need faster speed
            }
        }
        return left;
    }

private:
    bool canFinish(const std::vector<int>& piles, int h, int k) {
        long long hours = 0; // Use long long to prevent overflow
        for (int p : piles) {
            // Integer ceiling division
            hours += (p + k - 1) / k;
        }
        return hours <= h;
    }
};

6. Capacity to Ship Packages

Problem: Min capacity to ship in D days.

Range: [max(weights), sum(weights)].

#include <vector>
#include <numeric> // for std::accumulate
#include <algorithm> // for std::max_element

class Solution {
public:
    int shipWithinDays(std::vector<int>& weights, int days) {
        int left = *std::max_element(weights.begin(), weights.end());
        int right = std::accumulate(weights.begin(), weights.end(), 0);

        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // Check if capacity 'mid' is feasible
            int currentDays = 1;
            int currentLoad = 0;
            
            for (int w : weights) {
                if (currentLoad + w > mid) {
                    currentDays++;
                    currentLoad = 0;
                }
                currentLoad += w;
            }

            if (currentDays <= days) {
                right = mid; // Feasible, try smaller
            } else {
                left = mid + 1; // Not feasible, need larger
            }
        }
        return left;
    }
};

Summary of Binary Search Patterns

Problem Type	Search Space	Loop Condition	Update Logic
Exact Value	Array Index	left <= right	mid+1, mid-1
Boundary (LB)	Array Index	left < right	right = mid, left = mid+1
Boundary (UB)	Array Index	left < right	right = mid, left = mid+1
Rotated Array	Array Index	left <= right	Check sorted half first.
Answer Space	Integer Range	left < right	right = mid (if Valid), left = mid+1