Binary Search on the Answer

P(x) = False, False, ..., False, True, True, ..., True
                                 ^
                          find this boundary

// MINIMIZE pattern (LC 410, 1011)
while (left < right) {
    int mid = left + (right - left) / 2;  // Standard mid
    if (isValid(mid)) right = mid;        // Try smaller
    else left = mid + 1;
}
return left;

// MAXIMIZE pattern (LC 1231, 1552)
while (left < right) {
    int mid = left + (right - left + 1) / 2;  // CRITICAL: +1 to avoid infinite loop!
    if (isValid(mid)) left = mid;             // Try larger
    else right = mid - 1;
}
return left;

# python
# LC 875 - Koko Eating Bananas
# IDEA: binary search the speed; can_finish(speed) is monotone, so find its first True
# time = O(n log M), space = O(1)   M = max(piles)
def minEatingSpeed(piles, h):
    def can_finish(speed):
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed   # ceil(pile / speed) without floats
        return hours <= h

    left, right = 1, max(piles)          # speed max(piles) finishes in len(piles) <= h hours
    while left < right:
        mid = left + (right - left) // 2  # lower mid: right = mid always shrinks the range
        if can_finish(mid):
            right = mid                  # mid works -> the answer is mid or smaller
        else:
            left = mid + 1               # mid fails -> the answer is above mid
    return left

// java
// LC 875 - Koko Eating Bananas
// IDEA: binary search the speed; canFinish(speed) is monotone, so find its first true
// time = O(n log M), space = O(1)   M = max(piles)
public int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);        // speed max(piles) always finishes
    }
    while (left < right) {
        int mid = left + (right - left) / 2;  // lower mid; never overflows
        if (canFinish(piles, h, mid)) {
            right = mid;                      // mid works -> answer is mid or smaller
        } else {
            left = mid + 1;                   // mid fails -> answer is above mid
        }
    }
    return left;
}

private boolean canFinish(int[] piles, int h, int speed) {
    long hours = 0;                           // long: 10^4 piles * 10^9 hours overflows int
    for (int pile : piles) {
        hours += (pile + (long) speed - 1) / speed;   // ceil without floats
    }
    return hours <= h;
}

piles = [3,6,7,11], h = 8          hours(speed) = sum of ceil(pile / speed)
left=1  right=11  mid=6   hours=1+1+2+2=6  <= 8  -> right=6
left=1  right=6   mid=3   hours=1+2+3+4=10 >  8  -> left=4
left=4  right=6   mid=5   hours=1+2+2+3=8  <= 8  -> right=5
left=4  right=5   mid=4   hours=1+2+2+3=8  <= 8  -> right=4
left=4  right=4   stop -> 4

# python
# LC 1552 - Magnetic Force Between Two Balls
# IDEA: binary search the minimum gap; can_place(gap) is monotone (smaller is easier), find its last True
# time = O(n log n + n log R), space = O(n)   R = max(position) - min(position)
def maxDistance(position, m):
    position = sorted(position)          # the greedy placement needs left-to-right order

    def can_place(gap):
        placed = 1                       # the first ball always goes at position[0]
        last = position[0]
        for p in position[1:]:
            if p - last >= gap:          # far enough from the previous ball -> place one
                placed += 1
                last = p
        return placed >= m

    left, right = 1, position[-1] - position[0]   # positions are distinct, so gap 1 always works
    while left < right:
        mid = left + (right - left + 1) // 2      # upper mid: left = mid always shrinks the range
        if can_place(mid):
            left = mid                   # mid works -> the answer is mid or larger
        else:
            right = mid - 1              # mid fails -> the answer is below mid
    return left

// java
// LC 1552 - Magnetic Force Between Two Balls
// IDEA: binary search the minimum gap with the upper mid; find the last gap canPlace accepts
// time = O(n log n + n log R), space = O(1) beyond the sort   R = max(position) - min(position)
public int maxDistance(int[] position, int m) {
    Arrays.sort(position);
    int left = 1;
    int right = position[position.length - 1] - position[0];
    while (left < right) {
        int mid = left + (right - left + 1) / 2;   // upper mid: left = mid always moves
        if (canPlace(position, m, mid)) {
            left = mid;                            // mid works -> answer is mid or larger
        } else {
            right = mid - 1;                       // mid fails -> answer is below mid
        }
    }
    return left;
}

private boolean canPlace(int[] position, int m, int gap) {
    int placed = 1;                                // first ball at position[0]
    int last = position[0];
    for (int i = 1; i < position.length; i++) {
        if (position[i] - last >= gap) {           // greedy: place as early as allowed
            placed++;
            last = position[i];
        }
    }
    return placed >= m;
}

position = [1,2,3,4,7], m = 3
left=1  right=6  mid=4   place 1, 7          -> 2 balls < 3  -> right=3
left=1  right=3  mid=2   place 1, 3, 7       -> 3 balls      -> left=2
left=2  right=3  mid=3   place 1, 4, 7       -> 3 balls      -> left=3
left=3  right=3  stop -> 3

# python
# LC 410 - Split Array Largest Sum
# IDEA: binary search the cap in [max(nums), sum(nums)]; greedy fill counts the fewest groups for a cap
# time = O(n log S), space = O(1)   S = sum(nums)
def splitArray(nums, k):
    def can_split(cap):
        groups = 1
        current = 0
        for num in nums:
            if current + num <= cap:     # num still fits in the current group
                current += num
            else:                        # close the group, start a new one with num
                groups += 1
                current = num
                if groups > k:           # early exit: already too many groups
                    return False
        return True

    left = max(nums)                     # a group must hold the largest element on its own
    right = sum(nums)                    # one group holding everything always works
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid                  # fits in <= k groups -> try a smaller cap
        else:
            left = mid + 1               # needs > k groups -> the cap must grow
    return left

// java
// LC 410 - Split Array Largest Sum
// IDEA: binary search the cap in [max(nums), sum(nums)]; greedy fill counts the fewest groups for a cap
// time = O(n log S), space = O(1)   S = sum(nums)
public int splitArray(int[] nums, int k) {
    int left = 0;
    int right = 0;
    for (int num : nums) {
        left = Math.max(left, num);   // lower bound: a group must hold the largest element
        right += num;                 // upper bound: one group holds everything
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canSplit(nums, k, mid)) {
            right = mid;              // fits -> try a smaller cap
        } else {
            left = mid + 1;           // too many groups -> the cap must grow
        }
    }
    return left;
}

private boolean canSplit(int[] nums, int k, int cap) {
    int groups = 1;
    int current = 0;
    for (int num : nums) {
        if (current + num <= cap) {
            current += num;
        } else {
            groups++;
            current = num;
            if (groups > k) {
                return false;
            }
        }
    }
    return true;
}

nums = [7,2,5,10,8], k = 2           search [10, 32]
left=10  right=32  mid=21   [7,2,5]=14 [10,8]=18        2 groups -> right=21
left=10  right=21  mid=15   [7,2,5]=14 [10] [8]         3 groups -> left=16
left=16  right=21  mid=18   [7,2,5]=14 [10,8]=18        2 groups -> right=18
left=16  right=18  mid=17   [7,2,5]=14 [10] [8]         3 groups -> left=18
left=18  right=18  stop -> 18

# python
# LC 378 - Kth Smallest Element in a Sorted Matrix
# IDEA: binary search the value range; first x with count(<= x) >= k is the answer
# time = O(n log(max - min)), space = O(1)
def kthSmallest(matrix, k):
    n = len(matrix)

    def count_at_most(x):
        # staircase from the bottom-left corner: each step drops a row or a column
        row, col = n - 1, 0
        count = 0
        while row >= 0 and col < n:
            if matrix[row][col] <= x:
                count += row + 1         # this cell and every cell above it are <= x
                col += 1
            else:
                row -= 1
        return count

    left, right = matrix[0][0], matrix[n - 1][n - 1]
    while left < right:
        mid = left + (right - left) // 2
        if count_at_most(mid) >= k:
            right = mid                  # at least k values <= mid -> answer is mid or smaller
        else:
            left = mid + 1               # fewer than k -> answer is above mid
    return left

// java
// LC 378 - Kth Smallest Element in a Sorted Matrix
// IDEA: binary search the value range; first x with countAtMost(x) >= k is the answer
// time = O(n log(max - min)), space = O(1)
public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int left = matrix[0][0];
    int right = matrix[n - 1][n - 1];
    while (left < right) {
        int mid = left + (right - left) / 2;   // floors even for negatives; (left + right) / 2 does not
        if (countAtMost(matrix, mid) >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private int countAtMost(int[][] matrix, int x) {
    int n = matrix.length;
    int row = n - 1;          // start bottom-left
    int col = 0;
    int count = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= x) {
            count += row + 1;  // the whole column above is <= x too
            col++;
        } else {
            row--;
        }
    }
    return count;
}

matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
left=1   right=15  mid=8    values <= 8: 1,5                      count=2 < 8  -> left=9
left=9   right=15  mid=12   1,5,9,10,11,12                         count=6 < 8  -> left=13
left=13  right=15  mid=14   1,5,9,10,11,12,13,13                   count=8 >= 8 -> right=14
left=13  right=14  mid=13   same eight                             count=8 >= 8 -> right=13
left=13  right=13  stop -> 13          (mid=14 also had count 8, but 14 is not in the matrix)

If we can achieve the goal with maximum value = X,
then we can ALWAYS achieve it with maximum value = X + 1 (or any larger value).

Answer Space:  0   1   2   3   4   5   6   7   8   9   ...
               |---|---|---|---|---|---|---|---|---|---|
Feasible?      ✗   ✗   ✗   ✗   ✓   ✓   ✓   ✓   ✓   ✓   ...
                           ↑
                    Decision Boundary (Answer = 4)

The feasibility function is monotonic:
- All values LEFT of boundary: INFEASIBLE (✗)
- All values RIGHT of boundary: FEASIBLE (✓)
- We want to find the LEFTMOST ✓ (minimum feasible value)

Problem: Find p=2 pairs with minimum maximum difference
Array after sorting: [1, 1, 2, 3, 7, 10]

Answer space (max diff): 0  1  2  3  4  5  6  7  8  9
Can form 2 pairs?        ✗  ✓  ✓  ✓  ✓  ✓  ✓  ✓  ✓  ✓
                            ↑
                     Answer = 1 (minimum max diff)

Why monotonic?
- If max_diff = 1 works: pairs (1,1)=0, (2,3)=1 → both ≤ 1 ✓
- If max_diff = 2 works: same pairs still work, more options available ✓
- If max_diff = 0 fails: only (1,1)=0 works, can't form 2 pairs ✗

Larger max_diff → More pairs possible → Easier to satisfy constraint

✅ Requirement 1: BOUNDED answer space
   - Must have clear [min, max] range
   - Example: [0, max_element - min_element]

✅ Requirement 2: MONOTONIC feasibility
   - If X works, X+1 must also work (for minimize)
   - If X works, X-1 must also work (for maximize)

✅ Requirement 3: EFFICIENT validation
   - Can check if answer X is valid in O(n) or O(n log n)
   - Usually uses greedy approach

# python
# LC 1283 - Find the Smallest Divisor Given a Threshold
# IDEA: first divisor in [1, max(nums)] whose sum of ceil(num / d) is <= threshold
# time = O(n log M), space = O(1)   M = max(nums)
def smallestDivisor(nums, threshold):
    def fits(divisor):
        total = 0
        for num in nums:
            total += (num + divisor - 1) // divisor   # ceil without floats
        return total <= threshold

    left, right = 1, max(nums)
    while left < right:
        mid = left + (right - left) // 2
        if fits(mid):
            right = mid
        else:
            left = mid + 1
    return left

// java
// LC 1283 - Find the Smallest Divisor Given a Threshold
// IDEA: first divisor whose sum of ceil(num / d) is <= threshold
// time = O(n log M), space = O(1)   M = max(nums)
public int smallestDivisor(int[] nums, int threshold) {
    int left = 1, right = 0;
    for (int num : nums) right = Math.max(right, num);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (divisionSum(nums, mid) <= threshold) right = mid;
        else left = mid + 1;
    }
    return left;
}

private long divisionSum(int[] nums, int divisor) {
    long total = 0;
    for (int num : nums) total += (num + divisor - 1) / divisor;
    return total;
}

# python
# LC 1482 - Minimum Number of Days to Make m Bouquets
# IDEA: first day d where runs of k open flowers make at least m bouquets
# time = O(n log D), space = O(1)   D = max(bloomDay) - min(bloomDay)
def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1                            # not enough flowers on any day

    def can_make(day):
        bouquets = 0
        run = 0                              # adjacent open flowers so far
        for bloom in bloomDay:
            if bloom <= day:
                run += 1
                if run == k:
                    bouquets += 1
                    run = 0                  # these k flowers are used
            else:
                run = 0                      # a closed flower breaks adjacency
        return bouquets >= m

    left, right = min(bloomDay), max(bloomDay)
    while left < right:
        mid = left + (right - left) // 2
        if can_make(mid):
            right = mid
        else:
            left = mid + 1
    return left

// java
// LC 1482 - Minimum Number of Days to Make m Bouquets
// IDEA: first day where runs of k open flowers make at least m bouquets
// time = O(n log D), space = O(1)
public int minDays(int[] bloomDay, int m, int k) {
    if ((long) m * k > bloomDay.length) return -1;   // m * k overflows int at 10^6 * 10^6
    int left = Integer.MAX_VALUE, right = 0;
    for (int day : bloomDay) {
        left = Math.min(left, day);
        right = Math.max(right, day);
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canMake(bloomDay, m, k, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

private boolean canMake(int[] bloomDay, int m, int k, int day) {
    int bouquets = 0, run = 0;
    for (int bloom : bloomDay) {
        if (bloom <= day) {
            run++;
            if (run == k) {
                bouquets++;
                run = 0;
            }
        } else {
            run = 0;
        }
    }
    return bouquets >= m;
}

# python
# LC 1539 - Kth Missing Positive Number
# IDEA: first index i with arr[i] - (i + 1) >= k; the answer is i + k
# time = O(log n), space = O(1)
def findKthPositive(arr, k):
    left, right = 0, len(arr)                # right = n: the answer can fall past the last element
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] - (mid + 1) < k:
            left = mid + 1                   # fewer than k missing before mid
        else:
            right = mid
    return left + k                          # left numbers of arr are below the answer

// java
// LC 1539 - Kth Missing Positive Number
// IDEA: first index with arr[i] - (i + 1) >= k; the answer is that index + k
// time = O(log n), space = O(1)
public int findKthPositive(int[] arr, int k) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] - (mid + 1) < k) left = mid + 1;
        else right = mid;
    }
    return left + k;
}

# python
# LC 2616 - Minimize the Maximum Difference of Pairs
# IDEA: sort; first cap x in [0, max - min] for which greedy adjacent pairing finds p pairs
# time = O(n log n + n log R), space = O(1) besides the sort   R = max - min
def minimizeMax(nums, p):
    nums.sort()

    def enough_pairs(cap):
        count = 0
        i = 0
        while i < len(nums) - 1:
            if nums[i + 1] - nums[i] <= cap:
                count += 1
                i += 2                       # both elements are used
            else:
                i += 1
        return count >= p

    left, right = 0, nums[-1] - nums[0]
    while left < right:
        mid = left + (right - left) // 2
        if enough_pairs(mid):
            right = mid
        else:
            left = mid + 1
    return left

// java
// LC 2616 - Minimize the Maximum Difference of Pairs
// IDEA: sort; first cap for which greedy adjacent pairing finds p pairs
// time = O(n log n + n log R), space = O(1) besides the sort
public int minimizeMax(int[] nums, int p) {
    Arrays.sort(nums);
    int left = 0, right = nums[nums.length - 1] - nums[0];
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (enoughPairs(nums, p, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

private boolean enoughPairs(int[] nums, int p, int cap) {
    int count = 0;
    int i = 0;
    while (i < nums.length - 1) {
        if (nums[i + 1] - nums[i] <= cap) {
            count++;
            i += 2;                      // both elements are used
        } else {
            i += 1;
        }
    }
    return count >= p;
}

nums = [10,1,2,7,1,3], p = 2  -> sorted [1,1,2,3,7,10]
left=0  right=9  mid=4   pairs (1,1) (2,3)        2 >= 2 -> right=4
left=0  right=4  mid=2   pairs (1,1) (2,3)        2 >= 2 -> right=2
left=0  right=2  mid=1   pairs (1,1) (2,3)        2 >= 2 -> right=1
left=0  right=1  mid=0   pairs (1,1)              1 <  2 -> left=1
left=1  right=1  stop -> 1

# python
# LC 1631 - Path With Minimum Effort
# IDEA: binary search the effort limit; feasibility = BFS that only takes steps with |diff| <= limit
# time = O(m * n * log H), space = O(m * n)   H = max height - min height
from collections import deque

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])

    def can_reach(limit):
        seen = [[False] * cols for _ in range(rows)]
        seen[0][0] = True
        queue = deque([(0, 0)])
        while queue:
            r, c = queue.popleft()
            if r == rows - 1 and c == cols - 1:
                return True
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]:
                    if abs(heights[nr][nc] - heights[r][c]) <= limit:
                        seen[nr][nc] = True
                        queue.append((nr, nc))
        return False

    highest = max(max(row) for row in heights)
    lowest = min(min(row) for row in heights)
    left, right = 0, highest - lowest
    while left < right:
        mid = left + (right - left) // 2
        if can_reach(mid):
            right = mid
        else:
            left = mid + 1
    return left

// java
// LC 1631 - Path With Minimum Effort
// IDEA: binary search the effort limit; feasibility = BFS reachability under the limit
// time = O(m * n * log H), space = O(m * n)
public int minimumEffortPath(int[][] heights) {
    int highest = Integer.MIN_VALUE, lowest = Integer.MAX_VALUE;
    for (int[] row : heights) {
        for (int h : row) {
            highest = Math.max(highest, h);
            lowest = Math.min(lowest, h);
        }
    }
    int left = 0, right = highest - lowest;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canReach(heights, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

private boolean canReach(int[][] heights, int limit) {
    int rows = heights.length, cols = heights[0].length;
    boolean[][] seen = new boolean[rows][cols];
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{0, 0});
    seen[0][0] = true;
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        if (cur[0] == rows - 1 && cur[1] == cols - 1) return true;
        for (int[] d : dirs) {
            int nr = cur[0] + d[0], nc = cur[1] + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc]
                    && Math.abs(heights[nr][nc] - heights[cur[0]][cur[1]]) <= limit) {
                seen[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    return false;
}

# python
# LC 1231 - Divide Chocolate
# IDEA: last x for which greedy cutting makes >= k + 1 pieces of sweetness >= x; upper mid
# time = O(n log S), space = O(1)   S = sum(sweetness)
def maximizeSweetness(sweetness, k):
    people = k + 1

    def can_cut(target):
        pieces = 0
        current = 0
        for s in sweetness:
            current += s
            if current >= target:            # this piece is sweet enough: cut it here
                pieces += 1
                current = 0
        return pieces >= people              # leftover sweetness joins the last piece

    left, right = min(sweetness), sum(sweetness) // people
    while left < right:
        mid = left + (right - left + 1) // 2  # upper mid: left = mid must move
        if can_cut(mid):
            left = mid
        else:
            right = mid - 1
    return left

// java
// LC 1231 - Divide Chocolate
// IDEA: last x for which greedy cutting makes >= k + 1 pieces of sweetness >= x; upper mid
// time = O(n log S), space = O(1)
public int maximizeSweetness(int[] sweetness, int k) {
    int people = k + 1;
    int left = Integer.MAX_VALUE, sum = 0;
    for (int s : sweetness) {
        left = Math.min(left, s);
        sum += s;
    }
    int right = sum / people;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (canCut(sweetness, people, mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

private boolean canCut(int[] sweetness, int people, int target) {
    int pieces = 0, current = 0;
    for (int s : sweetness) {
        current += s;
        if (current >= target) {
            pieces++;
            current = 0;
        }
    }
    return pieces >= people;
}

sweetness = [1,2,3,4,5,6,7,8,9], k = 5   -> 6 pieces, search [1, 45 // 6 = 7]
left=1  right=7  mid=4   [1,2,3][4][5][6][7][8][9]   7 pieces >= 6 -> left=4
left=4  right=7  mid=6   [1,2,3][4,5][6][7][8][9]    6 pieces >= 6 -> left=6
left=6  right=7  mid=7   [1,2,3,4][5,6][7][8][9]     5 pieces <  6 -> right=6
left=6  right=6  stop -> 6

# python
# LC 1011 - Capacity To Ship Packages Within D Days
# IDEA: first capacity in [max(weights), sum(weights)] whose greedy loading needs <= days days
# time = O(n log S), space = O(1)   S = sum(weights)
def shipWithinDays(weights, days):
    def can_ship(capacity):
        needed = 1
        load = 0
        for weight in weights:
            if load + weight <= capacity:
                load += weight
            else:
                needed += 1                  # this package starts a new day
                load = weight
                if needed > days:
                    return False
        return True

    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    return left

// java
// LC 1011 - Capacity To Ship Packages Within D Days
// IDEA: first capacity in [max, sum] whose greedy loading needs <= days days
// time = O(n log S), space = O(1)
public int shipWithinDays(int[] weights, int days) {
    int left = 0, right = 0;
    for (int weight : weights) {
        left = Math.max(left, weight);   // a day must carry the heaviest package
        right += weight;                 // one day carries everything
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canShip(weights, days, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

private boolean canShip(int[] weights, int days, int capacity) {
    int needed = 1, load = 0;
    for (int weight : weights) {
        if (load + weight <= capacity) {
            load += weight;
        } else {
            needed++;
            load = weight;
            if (needed > days) return false;
        }
    }
    return true;
}

# python
# LC 287 - Find the Duplicate Number
# IDEA: first value v in [1, n] with count(<= v) > v (pigeonhole); the array is never modified
# time = O(n log n), space = O(1)
def findDuplicate(nums):
    left, right = 1, len(nums) - 1          # values are in [1, n], n = len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        count = 0
        for x in nums:
            if x <= mid:
                count += 1
        if count > mid:
            right = mid                     # too many values <= mid: the duplicate is <= mid
        else:
            left = mid + 1                  # the duplicate is above mid
    return left

// java
// LC 287 - Find the Duplicate Number
// IDEA: first value v with count(<= v) > v (pigeonhole)
// time = O(n log n), space = O(1)
public int findDuplicate(int[] nums) {
    int left = 1, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int x : nums) if (x <= mid) count++;
        if (count > mid) right = mid;
        else left = mid + 1;
    }
    return left;
}