1
l, r = min_valid, max_feasible
2
while l <= r:
3
    mid = l + (r - l) // 2
4
    if check(mid): # Feasible, but look for smaller ones to the left
5
        r = mid - 1
6
    else:          # Not feasible, must increase x
7
        l = mid + 1
8
return l  # When loop ends, l points to the first True

1
while l <= r:
2
    mid = l + (r - l) // 2
3
    if check(mid): # Feasible, try to find a larger one to the right
4
        l = mid + 1
5
    else:          # Not feasible, must decrease x
6
        r = mid - 1
7
return r  # When loop ends, r points to the last True

1
Input: nums = [1,2,5,9], threshold = 6
2
Output: 5
3
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
4
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

1
Input: nums = [44,22,33,11,1], threshold = 5
2
Output: 44

1
# Note: You don't need to sort the input array here because the answer is not required to be an element of the array; we are searching within the range from 1 to max(nums).
2
class Solution:
3
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
4
        l, r = 1, max(nums)
5
        while l <= r:
6
            m = (l + r) // 2
7
            total = 0
8
            if sum((x + m - 1) // m for x in nums) <= threshold:
9
                r = m - 1
10
            else:
11
                l = m + 1
12
        return l

1
Input: time = [1,2,3], totalTrips = 5
2
Output: 3
3
Explanation:
4
- At time t = 1, the number of trips completed by each bus are [1,0,0].
5
  The total number of trips completed is 1 + 0 + 0 = 1.
6
- At time t = 2, the number of trips completed by each bus are [2,1,0].
7
  The total number of trips completed is 2 + 1 + 0 = 3.
8
- At time t = 3, the number of trips completed by each bus are [3,1,1].
9
  The total number of trips completed is 3 + 1 + 1 = 5.
10
So the minimum time needed for all buses to complete at least 5 trips is 3.

1
Input: time = [2], totalTrips = 1
2
Output: 2
3
Explanation:
4
There is only one bus, and it will complete its first trip at t = 2.
5
So the minimum time needed to complete 1 trip is 2.

1
# Ensure that the right boundary is large enough to cover totalTrips. The most reliable way is min(time) * totalTrips.
2
class Solution:
3
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
4
        min_t = min(time)
5
        l = min_t
6
        r = min_t * totalTrips
7
        while l <= r:
8
            m = (l + r) // 2
9
            if sum(m // x for x in time) >= totalTrips:
10
                r = m - 1
11
            else:
12
                l = m + 1
13
        # After the loop, 'l' is the smallest time that satisfies the condition
14
        return l

1
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
2
Output: 15
3
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
4
1st day: 1, 2, 3, 4, 5
5
2nd day: 6, 7
6
3rd day: 8
7
4th day: 9
8
5th day: 10
9

10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

1
Input: weights = [3,2,2,4,1,4], days = 3
2
Output: 6
3
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
4
1st day: 3, 2
5
2nd day: 2, 4
6
3rd day: 1, 4

1
Input: weights = [1,2,3,1,1], days = 4
2
Output: 3
3
Explanation:
4
1st day: 1
5
2nd day: 2
6
3rd day: 3
7
4th day: 1, 1

1
class Solution:
2
    def shipWithinDays(self, weights: List[int], days: int) -> int:
3
        # l: must be at least the heaviest package
4
        # r: the sum of all packages (shipping everything in 1 day)
5
        l, r = max(weights), sum(weights)
6

7
        while l <= r:
8
            mid = (l + r) // 2
9

10
            # Greedy check: how many days are needed with capacity 'mid'?
11
            need = 1
12
            cur = 0
13
            for w in weights:
14
                if cur + w <= mid:
15
                    cur += w
16
                else:
17
                    need += 1
18
                    cur = w # Start new day with the current package
19

20
            if need <= days:
21
                # Valid capacity, try to find a smaller one
22
                r = mid - 1
23
            else:
24
                # Capacity too small, need more power
25
                l = mid + 1
26
        return l

1
Input: houses = [1,2,3], heaters = [2]
2
Output: 1
3
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

1
Input: houses = [1,2,3,4], heaters = [1,4]
2
Output: 1
3
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

1
Input: houses = [1,5], heaters = [2]
2
Output: 3

1
# Strategy: For each house, find the nearest heaters on both the left and right sides.
2
# The minimum radius required for a house is the distance to its closest heater.
3
# The global answer is the maximum of these minimum distances.
4
class Solution:
5
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
6
        ans = 0
7
        houses.sort()
8
        heaters.sort()
9
        n = len(heaters)
10

11
        for x in houses:
12
            # Binary Search for the first heater >= house (Lower Bound)
13
            i = bisect.bisect_left(heaters, x)
14

15
            # Distance to the nearest heater on the left (largest heater <= x)
16
            # If i == 0, no heater exists on the left
17
            ld = x - heaters[i - 1] if i > 0 else float('inf')
18

19
            # Distance to the nearest heater on the right (smallest heater >= x)
20
            # If i == n, no heater exists on the right
21
            rd = heaters[i] - x if i < n else float('inf')
22

23
            # The house only needs to be covered by the CLOSER of the two
24
            # Update global max radius to ensure this house (and all others) are covered
25
            ans = max(ans, min(ld, rd))
26

27
        return ans

1
Input: piles = [3,6,7,11], h = 8
2
Output: 4

1
Input: piles = [30,11,23,4,20], h = 5
2
Output: 30

1
Input: piles = [30,11,23,4,20], h = 6
2
Output: 23

1
class Solution:
2
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
3
        # l: Smallest possible speed (1 banana/hr)
4
        # r: A "guaranteed feasible" upper bound (sum of all bananas)
5
        l = 1
6
        r = sum(piles) # Note: max(piles) is a tighter, more efficient bound
7

8
        while l <= r:
9
            m = (l + r) // 2
10

11
            # check(m): Calculate total hours needed at speed 'm'
12
            # (x + m - 1) // m is the integer version of math.ceil(x / m)
13
            hours_needed = sum((x + m - 1) // m for x in piles)
14

15
            if hours_needed <= h:
16
                # current speed 'm' is feasible (True), try a smaller speed
17
                r = m - 1
18
            else:
19
                # current speed 'm' is too slow (False), must increase speed
20
                l = m + 1
21

22
        # After the loop, l is the first speed that makes check(m) True
23
        return l

1
Input: citations = [0,1,3,5,6]
2
Output: 3
3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
4
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

1
Input: citations = [1,2,100]
2
Output: 2

1
class Solution:
2
    def hIndex(self, citations: List[int]) -> int:
3
        n = len(citations)
4
        # Search Range: 0 to n (Max possible H-index is the number of papers)
5
        l, r = 0, n
6

7
        # Pattern: T T T...F F F (Looking for the LAST True)
8
        while l <= r:
9
            h = (l + r) // 2
10

11
            # check(h): Are there at least 'h' papers with >= 'h' citations?
12
            # Since sorted, citations[n-h] is the h-th largest value.
13
            if h == 0 or citations[n - h] >= h:
14
                # This 'h' works! Try a larger value to the right.
15
                l = h + 1
16
            else:
17
                # Too many papers requested or citations too low. Search left.
18
                r = h - 1
19

20
        # Per the "Last True" template, 'r' is the answer after l > r
21
        return r

1
Input: [1,12,-5,-6,50,3], k = 4
2
Output: 12.75
3
Explanation:
4
when length is 5, maximum average value is 10.8,
5
when length is 6, maximum average value is 9.16667.
6
Thus return 12.75.

1
class Solution:
2
    def findMaxAverage(self, nums: List[int], k: int) -> float:
3
        n = len(nums)
4

5
        def check(mid: float) -> bool:
6
            # Transform: sum(nums[i] - mid) >= 0
7
            pre = 0.0      # sum(b[0..i])
8
            pre_k = 0.0    # sum(b[0..i-k])
9
            min_pre = 0.0  # min(pre[0...i-k])
10

11
            # Initial window of size k
12
            for i in range(k):
13
                pre += nums[i] - mid
14
            if pre >= 0: return True
15

16
            # Sliding window with variable start
17
            for i in range(k, n):
18
                pre += nums[i] - mid
19
                pre_k += nums[i - k] - mid
20
                # Greedy: keep track of the smallest prefix sum seen so far
21
                # that allows for a subarray length >= k
22
                min_pre = min(min_pre, pre_k)
23

24
                if pre - min_pre >= 0:
25
                    return True
26
            return False
27

28
        # Range: Between the smallest and largest possible numbers
29
        l, r = min(nums), max(nums)
30
        eps = 1e-5 # Precision threshold
31

32
        # Binary search for the maximum feasible average
33
        while r - l > eps:
34
            mid = (l + r) / 2
35
            if check(mid):
36
                l = mid  # mid is feasible, try to increase it
37
            else:
38
                r = mid  # mid is too high, decrease it
39

40
        return l

1
Input: candies = [5,8,6], k = 3
2
Output: 5
3
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

1
Input: candies = [2,5], k = 11
2
Output: 0
3
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

1
# In binary search for the **maximum** value (`TTTTFFFF`), we move the left boundary (`l = m + 1`) when the condition is met to seek a larger valid answer, ultimately returning **`r`** as the last "True" position.
2
class Solution:
3
    def maximumCandies(self, candies: List[int], k: int) -> int:
4
        def ok(m):
5
            cnt = 0
6
            for x in candies:
7
                cnt += x // m
8
                if cnt >= k:
9
                    return True
10
            return False
11
        l = 1
12
        r = max(candies)
13
        while l <= r:
14
            m = (l + r) // 2
15
            if ok(m):
16
                l = m + 1
17
            else:
18
                r = m - 1
19
        return r

1
Input: nums = [3,2,1,5,6,4], k = 2
2
Output: 5

1
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
2
Output: 4

1
class Solution:
2
    def findKthLargest(self, nums: List[int], k: int) -> int:
3
        l = min(nums)
4
        r = max(nums)
5
        while l <= r:
6
            m = (l + r) // 2
7
            cnt = sum(x >= m for x in nums)
8
            if cnt >= k:
9
                l = m + 1
10
            else:
11
                r = m - 1
12
        return r

1
// std::numeric_limits<int>::min()
2
// std::numeric_limits<int>::max()
3
class Solution {
4
public:
5
    int findKthLargest(vector<int>& nums, int k) {
6
        auto [mn, mx] = minmax_element(nums.begin(), nums.end());
7
        int l = *mn;
8
        int r = *mx;
9
        auto checkKLargest = [&](int m) {
10
            int cnt = 0;
11
            for (int x : nums) {
12
                if (x >= m) cnt++;
13
            }
14
            return cnt >= k;
15
        };
16
        while (l <= r) {
17
            int m = l + (r - l) / 2;
18
            if (checkKLargest(m)) {
19
                l = m + 1;
20
            } else {
21
                r = m - 1;
22
            }
23
        }
24
        return r;
25
    }
26
};

1
array
2
target
3
nums

1
array
2
target
3
nums

1
# Exponential expansion is a method used to find a valid search boundary when the size of a sorted array is unknown or unbounded.
2
def doubling_search(nums, target):
3
    l = 0
4
    r = 1
5
    while True:
6
        try:
7
            if nums[r] < target:
8
                l = r
9
                r *= 2
10
            else:
11
                break
12
        except IndexError:
13
            break
14

15
    while l <= r:
16
        m = (l + r) // 2
17
        try:
18
            val = nums[m]
19
        except IndexError:
20
            r = m - 1
21
            continue
22

23
        if val > target:
24
            r = m - 1
25
        elif val == target:
26
            return m
27
        else:
28
            l = m + 1
29
    return -1