int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 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;
}

// We need to check every element including when lo == hi
// (single element remaining). Using lo < hi would skip
// the last comparison.
//
// Both lo and hi move PAST mid:
//   lo = mid + 1
//   hi = mid - 1
// This guarantees the search space shrinks every iteration.

int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length; // hi = length (past-end)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid; // nums[mid] >= target, could be answer
    }
    return lo; // first index where nums[i] >= target
}

// When nums[mid] >= target, mid MIGHT be the answer.
// We can't discard it. So hi = mid keeps it in the space.
// Combined with lo < hi and mid = lo + (hi-lo)/2,
// this guarantees convergence: when lo == hi, that's our answer.
//
// If we used hi = mid - 1 here, we could skip the actual answer.

int upperBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) lo = mid + 1;
        else hi = mid; // nums[mid] > target, could be answer
    }
    return lo; // first index where nums[i] > target
}

// The ONLY difference: the condition uses <= instead of <
// Lower bound: nums[mid] < target  → go right
// Upper bound: nums[mid] <= target → go right
//
// This means upper bound skips past elements EQUAL to target,
// landing on the first element strictly greater.

// Minimize x such that feasible(x) is true
int binarySearchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) {
            hi = mid; // mid works, but maybe smaller works too
        } else {
            lo = mid + 1; // mid doesn't work, need bigger
        }
    }
    return lo;
}

// Maximize x such that feasible(x) is true
int binarySearchOnAnswerMax(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2; // ceil division!
        if (feasible(mid)) {
            lo = mid; // mid works, but maybe bigger works too
        } else {
            hi = mid - 1; // mid doesn't work, need smaller
        }
    }
    return lo;
}

// When maximizing: lo = mid means lo might not advance.
// Example: lo=3, hi=4 → mid = 3 + (4-3)/2 = 3 → lo=3 → infinite loop!
// Fix: mid = lo + (hi - lo + 1) / 2 → mid = 3 + (4-3+1)/2 = 4
//
// Rule: if lo = mid is in your code, use CEILING division.
//        if hi = mid is in your code, use FLOOR division (default).

int searchRotated(int[] nums, int target) {
    int lo = 0, hi = nums.length - 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 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 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;
}

// In a rotated sorted array, at any mid point,
// at least ONE half is always perfectly sorted.
//
// Strategy:
// 1. Find which half is sorted (compare endpoints)
// 2. Check if target falls in the sorted half (simple range check)
// 3. If yes → search that half. If no → search the other half.
//
// This works because range checks are trivial on sorted segments.

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed; // ceiling division
    }
    return hours <= h;
}

int splitArray(int[] nums, int m) {
    int lo = Arrays.stream(nums).max().getAsInt(); // at least the largest element
    int hi = Arrays.stream(nums).sum(); // worst case: one group
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(nums, m, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

boolean canSplit(int[] nums, int m, int maxSum) {
    int groups = 1, currentSum = 0;
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            groups++;
            currentSum = num;
            if (groups > m) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

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

int[] searchRange(int[] nums, int target) {
    int first = lowerBound(nums, target);
    if (first == nums.length || nums[first] != target) {
        return new int[]{-1, -1};
    }
    int last = upperBound(nums, target) - 1;
    return new int[]{first, last};
}

int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int upperBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int minEatingSpeed(int[] piles, int h) {
    int lo = 1;
    int hi = 0;
    for (int p : piles) hi = Math.max(hi, p);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) {
            hi = mid; // mid works, try slower
        } else {
            lo = mid + 1; // mid too slow
        }
    }
    return lo;
}

boolean canFinish(int[] piles, int speed, int h) {
    int totalHours = 0;
    for (int pile : piles) {
        totalHours += (pile + speed - 1) / speed;
        if (totalHours > h) return false; // early exit
    }
    return true;
}