Binary Search

// ── TEMPLATE 1: Classic exact search ────────────────────────
// Use when: searching for an exact value in a sorted array.
// Loop exits when lo > hi (element not found).
int bsClassic(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (a[mid] == target) return mid;   // found
        else if (a[mid] <  target) lo = mid + 1; // target in right half
        else                       hi = mid - 1; // target in left half
    }
    return -1; // not found
}

// ── TEMPLATE 2: Lower bound ──────────────────────────────────
// Use when: find first index where a[i] >= target.
// Loop exits when lo == hi == insertion point.
int lowerBound(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size(); // hi = n (one past end) is valid
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1; // mid is too small, exclude it
        else                 hi = mid;      // mid could be the answer, keep it
    }
    return lo; // first index with a[lo] >= target
}

// ── TEMPLATE 3: Upper bound ──────────────────────────────────
// Use when: find first index where a[i] > target.
int upperBound(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1; // mid is not strictly greater
        else                  hi = mid;
    }
    return lo; // first index with a[lo] > target
}
// C++ equivalents: lower_bound(a.begin(),a.end(),t) and upper_bound(...)

Classic Binary Search: Target = 7
  Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]   target = 7
  Index:  0  1  2  3  4   5   6   7   8   9

  Iteration 1: lo=0, hi=9, mid=4, a[mid]=9
    9 > 7  =>  search left half.  hi = mid-1 = 3.
  [1, 3, 5, 7] [9, 11, 13, 15, 17, 19]
   lo=0      hi=3

  Iteration 2: lo=0, hi=3, mid=1, a[mid]=3
    3 < 7  =>  search right half.  lo = mid+1 = 2.
  [1, 3] [5, 7]
          lo=2 hi=3

  Iteration 3: lo=2, hi=3, mid=2, a[mid]=5
    5 < 7  =>  lo = mid+1 = 3.
         [7]
          lo=3=hi=3

  Iteration 4: lo=3, hi=3, mid=3, a[mid]=7
    7 == 7  =>  FOUND at index 3.

  Total comparisons: 4 = ceil(log2(10)).  Without binary search: up to 10.

Lower Bound and Upper Bound Trace
  Array: [1, 3, 3, 3, 5, 7, 9]   target = 3
  Index:  0  1  2  3  4  5  6
  Goal: find FIRST index where a[i] >= 3  (first occurrence of 3)

  lo=0, hi=7 (n=7, one past end)

  Iteration 1: mid=3, a[3]=3
    3 >= target=3  =>  hi = mid = 3.  (keep mid as candidate)
  lo=0, hi=3

  Iteration 2: mid=1, a[1]=3
    3 >= 3  =>  hi = 1.
  lo=0, hi=1

  Iteration 3: mid=0, a[0]=1
    1 < 3  =>  lo = mid+1 = 1.
  lo=1, hi=1  =>  loop exits (lo == hi).

  Return lo = 1.  a[1] = 3 = first occurrence.  Correct!

  Upper bound (first index > 3): returns 4.
  So all occurrences of 3 are in indices [1, 4) = {1, 2, 3}.
  Count of 3s = upperBound - lowerBound = 4 - 1 = 3.  Correct!

Binary Search on Answer Space: Koko Bananas
  Problem: Koko eats bananas. Piles = [3, 6, 7, 11]. H = 8 hours.
  Find minimum eating speed k such that Koko finishes all piles in H hours.

  Key insight: 'Can Koko finish at speed k?' is monotone.
  If YES at speed k, then YES at speed k+1, k+2, ... (faster is always feasible).
  If NO  at speed k, then NO  at speed k-1, k-2, ... (slower is never feasible).
  => Binary search on k!

  Search space: lo=1 (min possible speed), hi=11 (max pile = always works).

  mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8. YES
  hi = 6.

  mid=3: hours = ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8. NO
  lo = 4.

  mid=5: hours = ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 <= 8. YES
  hi = 5.

  mid=4: hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8. YES
  hi = 4.

  lo=4 == hi=4  =>  return 4.
  Answer: minimum speed = 4.  Correct!

Rotated Array: Which Half Is Sorted?
  Original sorted: [1, 2, 3, 4, 5, 6, 7]
  Rotated at index 3: [4, 5, 6, 7, 1, 2, 3]
  Index:               0  1  2  3  4  5  6

  Key property: at least ONE half is always normally sorted.
  Check: if a[lo] <= a[mid]  =>  left half [lo..mid] is sorted.
         else                =>  right half [mid..hi] is sorted.

  Search for target = 1:
  lo=0, hi=6, mid=3, a[mid]=7.
    a[lo]=4 <= a[mid]=7  =>  LEFT half [0..3] = [4,5,6,7] is sorted.
    Is target 1 in [4, 7]?  1 < 4  =>  NO.  Search right: lo = 4.

  lo=4, hi=6, mid=5, a[mid]=2.
    a[lo]=1 <= a[mid]=2  =>  LEFT half [4..5] = [1,2] is sorted.
    Is target 1 in [1, 2]?  1 >= 1 and 1 <= 2  =>  YES.  Search left: hi = 5.

  lo=4, hi=5, mid=4, a[mid]=1.
    a[mid] == target  =>  FOUND at index 4.

// Rotated Sorted Array Search — O(log n)
// LeetCode 33 — Search in Rotated Sorted Array
// Time: O(log n)  Space: O(1)
// Key: at mid, exactly one half is normally sorted. Use that to guide search.
int search(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;

        // Determine which half is sorted
        if (a[lo] <= a[mid]) {           // left half [lo..mid] is sorted
            if (a[lo] <= target && target < a[mid])
                hi = mid - 1;            // target is in sorted left half
            else
                lo = mid + 1;            // target must be in right half
        } else {                         // right half [mid..hi] is sorted
            if (a[mid] < target && target <= a[hi])
                lo = mid + 1;            // target is in sorted right half
            else
                hi = mid - 1;            // target must be in left half
        }
    }
    return -1;
}

// Find Minimum in Rotated Array — O(log n)
// LeetCode 153 — Find Minimum in Rotated Sorted Array
// Time: O(log n)  Space: O(1)
// The minimum is always in the UNSORTED (rotated) half.
int findMin(vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi])
            lo = mid + 1;  // min is in right half (right is unsorted)
        else
            hi = mid;      // min is in left half or at mid
    }
    return a[lo]; // lo == hi == index of minimum
}
// Why compare with a[hi] not a[lo]?
// Comparing mid to hi tells us if the right side is 'out of order' (rotated).
// If a[mid] > a[hi]: right half wraps around, minimum is in [mid+1, hi].
// If a[mid] <= a[hi]: right half is sorted normally, minimum is in [lo, mid].

// Binary Search on Answer Space — O(n log(max_val))
// Generic answer-space binary search template
// Find minimum x such that feasible(x) is true.
int answerSpaceBS(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid))
            hi = mid;      // mid works, try smaller
        else
            lo = mid + 1;  // mid does not work, must go larger
    }
    return lo; // minimum feasible value
}

// Koko Eating Bananas (LC 875)
// feasible(k): can Koko eat all piles at speed k in H hours?
bool feasible(vector<int>& piles, int k, int H) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k; // ceil(p/k)
    return hours <= H;
}
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;
        if (feasible(piles, mid, h)) hi = mid;
        else                         lo = mid + 1;
    }
    return lo;
}

// Lower/Upper Bound Applications
// Count occurrences of target in sorted array
// Time: O(log n)  Space: O(1)
int countOccurrences(vector<int>& a, int target) {
    // lower_bound: first index with a[i] >= target
    int lo = (int)(lower_bound(a.begin(), a.end(), target) - a.begin());
    // upper_bound: first index with a[i] > target
    int hi = (int)(upper_bound(a.begin(), a.end(), target) - a.begin());
    return hi - lo; // number of elements equal to target
}

// First and last position of target (LC 34)
vector<int> searchRange(vector<int>& a, int target) {
    int first = (int)(lower_bound(a.begin(),a.end(),target) - a.begin());
    if (first == (int)a.size() || a[first] != target) return {-1,-1};
    int last  = (int)(upper_bound(a.begin(),a.end(),target) - a.begin()) - 1;
    return {first, last};
}

// Binary Search on 2D Matrix — O(log(mn)) and O(m+n)
// LeetCode 74 — Search a 2D Matrix
// Matrix: rows sorted, last element of row < first element of next row.
// => Treat as a flattened 1D sorted array of m*n elements.
// Time: O(log(m*n))  Space: O(1)
bool searchMatrix(vector<vector<int>>& mat, int target) {
    int m = mat.size(), n = mat[0].size();
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = mat[mid / n][mid % n];  // convert 1D index to 2D
        if      (val == target) return true;
        else if (val <  target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return false;
}

// LeetCode 240 — Search a 2D Matrix II
// Each row sorted, each column sorted (but rows don't connect).
// Use staircase search from top-right corner: O(m+n)
bool searchMatrixII(vector<vector<int>>& mat, int target) {
    int r = 0, c = (int)mat[0].size() - 1;  // start top-right
    while (r < (int)mat.size() && c >= 0) {
        if      (mat[r][c] == target) return true;
        else if (mat[r][c] >  target) c--;  // too big: move left
        else                          r++;  // too small: move down
    }
    return false;
}

// Capacity to Ship — O(n log sum)
// LeetCode 1011 — Capacity to Ship Packages Within D Days
// Find minimum ship capacity to deliver all packages within D days.
// Time: O(n log(sum))  Space: O(1)
class Solution {
    bool canShip(vector<int>& weights, int cap, int days) {
        int d = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) { d++; load = 0; } // start new day
            load += w;
        }
        return d <= days;
    }
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // lo: must hold heaviest package; hi: ship all at once
        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 (canShip(weights, mid, days)) hi = mid;
            else                             lo = mid + 1;
        }
        return lo;
    }
};

// Find Peak Element — O(log n)
// LeetCode 162 — Find Peak Element
// A peak is an element strictly greater than its neighbours.
// Time: O(log n)  Space: O(1)
// Key insight: always move toward the higher neighbour.
// A peak must exist in that direction (by the rising slope argument).
int findPeakElement(vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid+1])
            lo = mid + 1;  // slope going up: peak is to the right
        else
            hi = mid;      // slope going down: peak is at mid or left
    }
    return lo; // lo == hi == index of a peak
}

// Split Array Largest Sum — O(n log sum)
// LeetCode 410 — Split Array Largest Sum
// Split nums into k non-empty subarrays to minimise the largest subarray sum.
// Time: O(n log(sum))  Space: O(1)
class Solution {
    bool canSplit(vector<int>& nums, int k, int limit) {
        int parts = 1, curr = 0;
        for (int x : nums) {
            if (curr + x > limit) { parts++; curr = 0; }
            curr += x;
        }
        return parts <= k;
    }
public:
    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, k, mid)) hi = mid;
            else                        lo = mid + 1;
        }
        return lo;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = (int)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 [lo..mid] is sorted
                if (nums[lo] <= target && target < nums[mid])
                    hi = mid - 1;   // target in sorted left half
                else
                    lo = mid + 1;   // target in right half
            } else {
                // Right half [mid..hi] is sorted
                if (nums[mid] < target && target <= nums[hi])
                    lo = mid + 1;   // target in sorted right half
                else
                    hi = mid - 1;   // target in left half
            }
        }
        return -1;
    }
};

class Solution {
    // Can Koko finish all piles at speed k within h hours?
    bool feasible(vector<int>& piles, long long k, int h) {
        long long hours = 0;
        for (int p : piles)
            hours += (p + k - 1) / k; // ceil(p / k)
        return hours <= h;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1;
        int hi = *max_element(piles.begin(), piles.end());
        // Binary search: find minimum k where feasible(k) is true
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (feasible(piles, mid, h))
                hi = mid;      // mid works, try smaller
            else
                lo = mid + 1;  // mid too slow, need faster
        }
        return lo; // lo == hi == minimum feasible speed
    }
};