Binary Search

int mid = lo + (hi - lo) / 2;   // ✅ Always use this — avoids overflow
// NOT: (lo + hi) / 2           — lo+hi can overflow int if both ~2×10^9

int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
 
    while (lo <= hi) {              // Search space: [lo, hi] (inclusive)
        int mid = lo + (hi-lo)/2;
        if      (arr[mid] == target) return mid;   // Found
        else if (arr[mid] <  target) lo = mid + 1; // Target in right half
        else                         hi = mid - 1; // Target in left half
    }
    return -1;  // Not found
}
// Time: O(log n), Space: O(1)
// Loop exits when lo > hi (empty search space)
// Each iteration: lo=mid+1 or hi=mid-1 — always changes, guaranteed termination

// Find first index where arr[idx] >= target  (lower_bound behavior)
int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();  // hi = n (one past end)
 
    while (lo < hi) {                  // Search space: [lo, hi)
        int mid = lo + (hi-lo)/2;
        if (arr[mid] < target) lo = mid + 1;  // arr[mid] too small → move right
        else                   hi = mid;       // arr[mid] >= target → might be answer
    }
    return lo;  // lo == hi — first index with arr[idx] >= target
                // Returns n if no such element (all elements < target)
}
// Template B key rule: NEVER do hi = mid-1 in this template (loop won't terminate)
// Always: lo = mid+1 (left condition fails), hi = mid (right, potential answer)

int binarySearch(vector<int>& arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi-lo)/2;
    if      (arr[mid] == target) return mid;
    else if (arr[mid] <  target) return binarySearch(arr, target, mid+1, hi);
    else                         return binarySearch(arr, target, lo, mid-1);
}
// Time: O(log n), Space: O(log n) — recursion stack
// Prefer iterative to avoid stack overhead

// Demonstrates the infinite loop with hi=mid in Template A:
while (lo <= hi) {
    int mid = lo + (hi-lo)/2;
    if (condition) hi = mid;   // ❌ if lo==hi, mid==lo==hi → hi=lo → no progress
}
 
// Demonstrates why hi=mid works in Template B:
while (lo < hi) {
    int mid = lo + (hi-lo)/2;  // mid < hi always (when lo < hi, mid = (lo+hi)/2 < hi)
    if (condition) hi = mid;   // ✅ hi shrinks, guaranteed termination
}

#include <algorithm>
vector<int> arr = {1, 3, 3, 3, 5, 7, 9};
 
// lower_bound: iterator to FIRST element >= target
auto lb = lower_bound(arr.begin(), arr.end(), 3);
cout << *lb;                          // 3
cout << lb - arr.begin();             // Index: 1
 
// upper_bound: iterator to FIRST element > target
auto ub = upper_bound(arr.begin(), arr.end(), 3);
cout << *ub;                          // 5
cout << ub - arr.begin();             // Index: 4
 
// Count occurrences of target in sorted array:
int count = upper_bound(arr.begin(), arr.end(), 3)
          - lower_bound(arr.begin(), arr.end(), 3);  // 3
 
// equal_range: returns {lower_bound, upper_bound} as a pair
auto [lo, hi] = equal_range(arr.begin(), arr.end(), 3);
int count2 = hi - lo;   // 3
 
// Check if element exists:
bool exists = binary_search(arr.begin(), arr.end(), 3);   // true
 
// Find the closest element to target in sorted array:
int target = 4;
auto it = lower_bound(arr.begin(), arr.end(), target);
// it points to first element >= target (here: 5)
// Check it-1 for closest element < target (here: 3)

// lower_bound: returns index of FIRST element >= target (0..n)
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;
    }
    return lo;  // n if all elements < target
}
 
// upper_bound: returns index of FIRST element > target (0..n)
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;  // Only difference: <= instead of <
        else                    hi = mid;
    }
    return lo;  // n if all elements <= target
}

// 1. Find insertion position (Search Insert Position LC 35)
int searchInsert(vector<int>& arr, int target) {
    return lower_bound(arr.begin(), arr.end(), target) - arr.begin();
}
 
// 2. Count elements in range [a, b] in sorted array
int countInRange(vector<int>& arr, int a, int b) {
    return upper_bound(arr.begin(), arr.end(), b)
         - lower_bound(arr.begin(), arr.end(), a);
}
 
// 3. Find the floor of target (largest element <= target)
int floor(vector<int>& arr, int target) {
    auto it = upper_bound(arr.begin(), arr.end(), target);
    if (it == arr.begin()) return -1;  // No element <= target
    return *prev(it);
}
 
// 4. Find the ceiling of target (smallest element >= target)
int ceiling(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it == arr.end()) return -1;  // No element >= target
    return *it;
}
 
// 5. Coordinate compression (Chapter 14 recap)
auto getRank = [&](int val, vector<int>& sorted_arr) {
    return lower_bound(sorted_arr.begin(), sorted_arr.end(), val)
           - sorted_arr.begin() + 1;  // 1-indexed rank
};

// ── Template M1: Find MINIMUM value where condition is TRUE ─────────────────
// Use when: "minimize X such that condition(X) is satisfied"
int findMin(int lo, int hi, auto condition) {
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (condition(mid)) hi = mid;       // mid might be the answer → go left
        else                lo = mid + 1;   // mid fails → go right
    }
    return lo;   // Smallest value where condition is true
}
 
// ── Template M2: Find MAXIMUM value where condition is TRUE ─────────────────
// Use when: "maximize X such that condition(X) is satisfied"
int findMax(int lo, int hi, auto condition) {
    while (lo < hi) {
        int mid = lo + (hi-lo+1)/2;   // Round UP to avoid infinite loop!
        if (condition(mid)) lo = mid;       // mid works → go right (try larger)
        else                hi = mid - 1;   // mid fails → go left
    }
    return lo;   // Largest value where condition is true
}
// NOTE: The +1 in mid for Template M2 is CRITICAL.
// Without it: if lo=5, hi=6, mid=5. If condition(5)=true → lo=5 (no change → infinite loop)
// With  it:   if lo=5, hi=6, mid=6. If condition(6)=true → lo=6 (terminates)

bool canFinish(vector<int>& piles, int speed, int H) {
    long long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceil(p/speed)
    return hours <= H;
}
 
int minEatingSpeed(vector<int>& piles, int H) {
    int lo = 1;
    int hi = *max_element(piles.begin(), piles.end());  // Maximum possible speed
 
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (canFinish(piles, mid, H)) hi = mid;   // mid might be answer → try smaller
        else                          lo = mid + 1;
    }
    return lo;
}
// Time: O(n log M) where M = max pile size. Space: O(1)

bool canShip(vector<int>& weights, int capacity, int D) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > capacity) { days++; load = 0; }
        load += w;
    }
    return days <= D;
}
 
int shipWithinDays(vector<int>& weights, int days) {
    int lo = *max_element(weights.begin(), weights.end());  // Min: must fit heaviest
    int hi = accumulate(weights.begin(), weights.end(), 0); // Max: ship all in 1 day
 
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (canShip(weights, mid, days)) hi = mid;
        else                             lo = mid + 1;
    }
    return lo;
}
// Time: O(n log(sum)), Space: O(1)

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;
 
        // Determine which half is sorted
        if (nums[lo] <= nums[mid]) {
            // LEFT half [lo..mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;   // Target is in the sorted left half
            } else {
                lo = mid + 1;   // Target must be in right half
            }
        } else {
            // RIGHT half [mid..hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;   // Target is in the sorted right half
            } else {
                hi = mid - 1;   // Target must be in left half
            }
        }
    }
    return -1;
}
// Time: O(log n), Space: O(1)
 
/*
  nums = [4,5,6,7,0,1,2], target = 0
  lo=0, hi=6, mid=3, nums[3]=7
    Left sorted? nums[0]=4 <= nums[3]=7 ✓
    0 in [4..7)? 4<=0? No → go right, lo=4
  lo=4, hi=6, mid=5, nums[5]=1
    Left sorted? nums[4]=0 <= nums[5]=1 ✓
    0 in [0..1)? Yes → go left, hi=4
  lo=4, hi=4, mid=4, nums[4]=0 == 0 → return 4 ✓
*/

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]) {
            // Minimum is in the right half (the rotation wrap is there)
            lo = mid + 1;
        } else {
            // Minimum is in the left half (including mid)
            hi = mid;
        }
    }
    return nums[lo];
}
// Time: O(log n), Space: O(1)
 
/*
  nums = [3, 4, 5, 1, 2]
  lo=0, hi=4, mid=2, nums[2]=5 > nums[4]=2 → lo=3
  lo=3, hi=4, mid=3, nums[3]=1 < nums[4]=2 → hi=3
  lo=3=hi → return nums[3]=1 ✓
*/

bool searchWithDuplicates(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;
 
        // Handle duplicates: can't determine which half is sorted
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
            lo++; hi--;   // Shrink from both sides
        } 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;
}
// Time: O(log n) avg, O(n) worst (all duplicates)

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];    // Convert linear index to 2D
 
        if      (val == target) return true;
        else if (val <  target) lo = mid + 1;
        else                    hi = mid - 1;
    }
    return false;
}
// Time: O(log(m×n)), Space: O(1)

bool searchMatrixII(vector<vector<int>>& matrix, int target) {
    int row = 0, col = matrix[0].size() - 1;  // Start: top-right
 
    while (row < (int)matrix.size() && col >= 0) {
        if      (matrix[row][col] == target) return true;
        else if (matrix[row][col] >  target) col--;  // Current too big → go left
        else                                 row++;  // Current too small → go down
    }
    return false;
}
// Time: O(m + n) — each step eliminates a row or column
// NOT pure binary search but uses binary search intuition

// If only rows are sorted (not the matrix globally):
bool searchRowSorted(vector<vector<int>>& matrix, int target) {
    for (auto& row : matrix) {
        if (binary_search(row.begin(), row.end(), target)) return true;
    }
    return false;
}
// Time: O(m log n) — binary search in each row

// Find first index i in [0,n) where condition(arr[i]) is TRUE
// Assumption: array is of the form [F,F,...,F,T,T,...,T]
int findFirst(vector<int>& arr, auto condition) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (condition(arr[mid])) hi = mid;   // Could be answer → search left
        else                     lo = mid+1; // Not answer → search right
    }
    return lo;   // n if no element satisfies condition
}
 
// Example: find first index where arr[i] >= target
auto cond = [&](int x){ return x >= target; };
int idx = findFirst(arr, cond);

// Find last index i in [0,n) where condition(arr[i]) is TRUE
// Assumption: array is of the form [T,T,...,T,F,F,...,F]
int findLast(vector<int>& arr, auto condition) {
    int lo = 0, hi = (int)arr.size() - 1;
    int result = -1;
    while (lo <= hi) {
        int mid = lo + (hi-lo)/2;
        if (condition(arr[mid])) { result = mid; lo = mid+1; }  // Found, try right
        else                       hi = mid - 1;
    }
    return result;  // -1 if no element satisfies condition
}

// Split array into k groups, minimize the maximum group sum
// Feasibility: "can we split into k groups each with sum <= capacity?"
bool feasible(vector<int>& arr, int k, long long capacity) {
    long long curr = 0; int groups = 1;
    for (int x : arr) {
        if (curr + x > capacity) { groups++; curr = 0; }
        curr += x;
    }
    return groups <= k;
}
 
int splitArrayLargestSum(vector<int>& nums, int k) {
    long long lo = *max_element(nums.begin(), nums.end());  // Min: must hold largest
    long long hi = accumulate(nums.begin(), nums.end(), 0LL); // Max: one group
 
    while (lo < hi) {
        long long mid = lo + (hi-lo)/2;
        if (feasible(nums, k, mid)) hi = mid;
        else                        lo = mid + 1;
    }
    return lo;
}

// Place m elements in n positions, maximize the minimum distance
bool canPlace(vector<int>& pos, int m, int minDist) {
    int count = 1, last = pos[0];
    for (int i = 1; i < (int)pos.size(); i++) {
        if (pos[i] - last >= minDist) { count++; last = pos[i]; }
        if (count >= m) return true;
    }
    return false;
}
 
int maxMinDistance(vector<int>& positions, int m) {
    sort(positions.begin(), positions.end());
    int lo = 1;
    int hi = positions.back() - positions.front();
 
    while (lo < hi) {
        int mid = lo + (hi-lo+1)/2;   // Round UP for "maximize minimum"!
        if (canPlace(positions, m, mid)) lo = mid;
        else                             hi = mid - 1;
    }
    return lo;
}

// Find any peak element (element greater than both neighbors) — LC 162
// Key property: if arr[mid] < arr[mid+1], a peak exists in [mid+1, hi]
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;  // Ascending → peak is right
        else                          hi = mid;       // Descending → peak is here or left
    }
    return lo;
}
// Time: O(log n), Space: O(1)
// Works because: nums[-1] = nums[n] = -∞, so a peak must exist

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;
        else if (nums[mid] <  target) lo = mid + 1;
        else                          hi = mid - 1;
    }
    return -1;
}
// Time: O(log n), Space: O(1)

int searchInsert(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();   // hi = n (can insert at end)
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (nums[mid] < target) lo = mid + 1;
        else                    hi = mid;
    }
    return lo;   // First index where nums[idx] >= target
}
// Time: O(log n), Space: O(1)
// Equivalent to: lower_bound(nums.begin(), nums.end(), target) - nums.begin()

vector<int> searchRange(vector<int>& nums, int target) {
    int first = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
 
    if (first == (int)nums.size() || nums[first] != target) return {-1, -1};
 
    int last = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
    return {first, last};
}
// Time: O(log n), Space: O(1)

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]) {
            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 -1;
}
// Time: O(log n), Space: O(1)

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 in right half
        else                       hi = mid;       // Min is in left half (including mid)
    }
    return nums[lo];
}
// Time: O(log n), Space: O(1)

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
 
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        long long hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;  // ceil(p/mid)
        if (hours <= h) hi = mid;
        else            lo = mid + 1;
    }
    return lo;
}
// Time: O(n log M) where M = max pile, Space: O(1)

int shipWithinDays(vector<int>& weights, int days) {
    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;
        int d = 1, curr = 0;
        for (int w : weights) {
            if (curr + w > mid) { d++; curr = 0; }
            curr += w;
        }
        if (d <= days) hi = mid;
        else           lo = mid + 1;
    }
    return lo;
}
// Time: O(n log(sum)), Space: O(1)

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;
        else if (val <  target) lo = mid + 1;
        else                    hi = mid - 1;
    }
    return false;
}
// Time: O(log(m×n)), Space: O(1)

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;  // Go toward peak
        else                          hi = mid;
    }
    return lo;
}
// Time: O(log n), Space: O(1)

int splitArray(vector<int>& nums, int k) {
    long long lo = *max_element(nums.begin(), nums.end());
    long long hi = accumulate(nums.begin(), nums.end(), 0LL);
 
    while (lo < hi) {
        long long mid = lo + (hi-lo)/2;
        // Feasibility: can we split into <= k parts each with sum <= mid?
        long long curr = 0; int parts = 1;
        for (int x : nums) {
            if (curr + x > mid) { parts++; curr = 0; }
            curr += x;
        }
        if (parts <= k) hi = mid;
        else            lo = mid + 1;
    }
    return lo;
}
// Time: O(n log(sum)), Space: O(1)

class TimeMap {
    unordered_map<string, vector<pair<int,string>>> store;  // key → [(timestamp, value)]
 
public:
    void set(string key, string value, int timestamp) {
        store[key].emplace_back(timestamp, value);
        // Note: timestamps are guaranteed increasing, so store is sorted by time
    }
 
    string get(string key, int timestamp) {
        if (!store.count(key)) return "";
        auto& v = store[key];
 
        // Binary search for largest timestamp <= given timestamp
        int lo = 0, hi = (int)v.size();
        while (lo < hi) {
            int mid = lo + (hi-lo)/2;
            if (v[mid].first <= timestamp) lo = mid + 1;
            else                           hi = mid;
        }
        // lo = first index with timestamp > given → lo-1 is the answer
        return lo > 0 ? v[lo-1].second : "";
    }
};
// set: O(1), get: O(log n) where n = number of entries for that key

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if (A.size() > B.size()) return findMedianSortedArrays(B, A);  // A is smaller
 
    int m = A.size(), n = B.size();
    int lo = 0, hi = m;
 
    while (lo <= hi) {
        int pa = lo + (hi-lo)/2;        // Partition A: pa elements from A in left half
        int pb = (m+n+1)/2 - pa;        // Partition B: remaining elements needed in left half
 
        int maxLeftA  = (pa == 0) ? INT_MIN : A[pa-1];
        int minRightA = (pa == m) ? INT_MAX : A[pa];
        int maxLeftB  = (pb == 0) ? INT_MIN : B[pb-1];
        int minRightB = (pb == n) ? INT_MAX : B[pb];
 
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
            // Correct partition found
            if ((m+n) % 2 == 1)
                return max(maxLeftA, maxLeftB);
            else
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.0;
        } else if (maxLeftA > minRightB) {
            hi = pa - 1;   // Too many elements from A in left half
        } else {
            lo = pa + 1;   // Too few elements from A in left half
        }
    }
    return 0.0;
}
// Time: O(log(min(m,n))), Space: O(1)
 
/*
  Key idea: find partition point pa (# elements from A in left half)
  Such that: maxLeft(A) <= minRight(B) AND maxLeft(B) <= minRight(A)
  Then the median is in {max(maxLeftA,maxLeftB), min(minRightA,minRightB)}
 
  A = [1,3], B = [2]  → median = 2
  pa=1, pb=1: maxLeftA=1, minRightA=3, maxLeftB=2, minRightB=MAX
  1 <= MAX ✓, 2 <= 3 ✓ → median = max(1,2) = 2 ✓
*/