# Binary Search To Find An Answer

#### [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)

```java
public int findDuplicate(int[] nums) {
    int lo = 1, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (findSmall(nums, mid)) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

private boolean findSmall(int[] nums, int target) {
    int count = 0;
    for (int num : nums) {
        if (num <= target) {
            count++;
        }
    }
    return count <= target;
}
```

#### [1011. Capacity To Ship Packages In N Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)

For problems such as *410*, *875*, *1011*, *1231*, it is hard to start. It has pre-conditions:

* Choose data from an array
* Must choose consecutively
* Can be determined by "try out"&#x20;
* Asking for a "min" or "max" of the choice

The problem asks if can be divide the array by a number and having the min/max of this range. Search in a range between the max of all numbers and the sum of all numbers. Use a helper function to try all numbers of the range, and find the min/max.&#x20;

Instead of trying all numbers, we can use binary search to quickly determine the result.&#x20;

*T: O(N\*log(range\_size))   S: O(1)*&#x20;

```java
public int shipWithinDays(int[] weights, int D) {
    int max = Integer.MIN_VALUE;
    int sum = 0;
    for (int w : weights) {
        max = Math.max(max, w);
        sum += w;
    }
    int left = max, right = sum;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canDivide(weights, mid, D)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

/*
*Determine if the array can split into D continuous subarrays, 
 and each subarray sum can fit (<=) capacity
*/
private boolean canDivide(int[] weights, int capacity, int D) {
    int sum = 0, count = 1;
    for (int w : weights) {
        if (sum + w > capacity) {
            sum = 0;
            if (count++ > D) return false;
        }
        sum += w;
    }
    return count <= D;
}
```

#### [410. Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)

```java
public int splitArray(int[] nums, int m) {
    int sum = 0, max = Integer.MIN_VALUE;
    for (int n : nums) {
        sum += n;
        max = Math.max(max, n);
    }
    
    int lo = max, hi = sum;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canDivide(nums, mid, m)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

/*
*Determine if the array can split into m continuous subarrays, 
 and each subarray sum is smaller than sum val
*/
private boolean canDivide(int[] nums, int val, int m) {
    int sum = 0, count = 1;
    for (int n : nums) {
        if (sum + n > val) {
            count++;
            sum = 0;
            if (count > m) {
                return false;
            }
        }
        sum += n;
    }
    return true;
}
```

#### [1231. Divide Chocolate](https://leetcode.com/problems/divide-chocolate/)

Divide the array into K continuous subarrays, maximize the min share of this array

```java
public int maximizeSweetness(int[] sweetness, int K) {
    int sum = 0, min = sweetness[0];
    for (int n : sweetness) {
        sum += n;
        min = Math.min(min, n);
    }
    int L = min, R = sum;
    while (L < R) {
        int mid = L + (R - L + 1) / 2;
        if (canDivide(sweetness, mid, K)) {
            L = mid;
        } else {
            R = mid - 1;
        }
    }
    return L;
}

private boolean canDivide(int[] sweet, int t, int K) {
    int groupcount = 0, sum = 0;
    for (int n : sweet) {
        sum += n;
        if (sum >= t) {
            groupcount++;
            sum = 0;
        }
    }
    return groupcount > K;
}
```

#### [875. Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/)

```java
public int minEatingSpeed(int[] piles, int H) {
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }
    int left = 0;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(piles, H, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean canEatAll(int[] piles, int h, int k) {
    int hours = 0;
    for (int p : piles) {
        hours += Math.ceil(1.0 * p / k);
    }
    return hours <= h;
}
```

#### [774. Minimize Max Distance to Gas Station](https://leetcode.com/problems/minimize-max-distance-to-gas-station/)

```java
public double minmaxGasDist(int[] stations, int k) {
    double left = 0, right = 1e8;
    while (right - left > 1e-6) {
        double mid = (left + right) / 2.0;
        if (isValid(stations, k, mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return left;
}

private boolean isValid(int[] stations, int k, double d) {
    int used = 0;
    for (int i = 0; i < stations.length - 1; i++) {
        used += (int) ((stations[i + 1] - stations[i]) / d);
    }
    return used <= k;
}
```

Find the Smallest Divisor Given a Threshold

Divide Chocolate

[424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)

[**1802. Maximum Value at a Given Index in a Bounded Array**](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/)

```java
public int maxValue(int n, int index, int maxSum) {
    int left = 1, right = maxSum;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (getSum(index, mid, n) <= maxSum) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

private long getSum(int index, int value, int n) {
    long count = 0;
    
    // On index's left:
    // If value > index, there are index + 1 numbers in the arithmetic sequence:
    // [value - index, ..., value - 1, value].
    // Otherwise, there are value numbers in the arithmetic sequence:
    // [1, 2, ..., value - 1, value], plus a sequence of length (index - value + 1) of 1s. 
    if (value > index) {
        count += (long)(value + value - index) * (index + 1) / 2;
    } else {
        count += (long)(value + 1) * value / 2 + index - value + 1;
    };
    // On index's right:
    // If value >= n - index, there are n - index numbers in the arithmetic sequence:
    // [value, value - 1, ..., value - n + 1 + index].
    // Otherwise, there are value numbers in the arithmetic sequence:
    // [value, value - 1, ..., 1], plus a sequence of length (n - index - value) of 1s. 
    if (value >= n - index) {
        count += (long)(value + value - n + 1 + index) * (n - index) / 2;
    } else {
        count += (long)(value + 1) * value / 2 + n - index - value;
    }   
    
    return count - value;
}
```

[2616. Minimize the Maximum Difference of Pairs](https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/)

```java
public int minimizeMax(int[] nums, int p) {
    Arrays.sort(nums);
    int n = nums.length;
    int left = 0, right = nums[n - 1] - nums[0];
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (countValidPairs(nums, mid) >= p) {
            right = mid;
        } else {
            left = mid + 1;
        }
    } 
    return left;
}

private int countValidPairs(int[] nums, int threshold) {
    int i = 0, count = 0;
    while (i < nums.length - 1) {
        if (nums[i + 1] - nums[i] <= threshold) {
            count++;
            i += 2; // skip the next one because it forms a pair with current
        } else {
            i++;
        }
    }
    return count;
}
```

**(NOT on LC) Maximum min absolute difference**

**Problem**:\
Given an integer array **nums** and an integer **d**, you can adjust each element of **nums** by adding any value up to d (including zero). Your goal is to modify the array such that the minimum absolute difference between any two elements in the adjusted array is maximized.\
**Example**:\
Given nums = \[6, 0, 3] and d = 2, one possible adjusted array is \[8, 0, 4]. The minimum absolute difference among these elements is 4 (the minimum of |8−4|, |4−0|, and |8−0|). Therefore, the maximum achievable minimum difference is 4.\
Given nums = \[1, 5, 9, 14] and d = 3, you can adjust each element by adding any value from 0 up to 3.\
One possible adjusted array is \[4, 5, 9, 14]. The pairwise absolute differences are:\
|4 - 5| = 1\
|5 - 9| = 4\
|9 - 14| = 5\
and others like |4 - 9| = 5, |5 - 14| = 9, |4 - 14| = 10\
The minimum difference here is 1. But adjusting to \[1, 5, 12, 14] gives differences:\
|1 - 5| = 4\
|5 - 12| = 7\
|12 - 14| = 2\
others: |1 - 12| = 11, |1 - 14| = 13, |5 - 14| = 9&#x20;

The minimum difference is now 2, which is larger than before. Your goal is to find such adjustments that maximize this minimum absolute difference.

```java
public int maximizeMinDifference(int[] nums, int d) {
    Arrays.sort(nums);
    int n = nums.length;
    int low = 0;
    int high = nums[n - 1] + d - nums[0];  // max possible difference

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canAdjust(nums, d, mid)) {
            low = mid + 1;  // try larger minimum difference
        } else {
            high = mid - 1; // try smaller
        }
    }
    return high;
}

private boolean canAdjust(int[] nums, int d, int minDiff) {
    // Adjust first element minimally
    long prev = nums[0];
    for (int i = 1; i < nums.length; i++) {
        // The minimum value to maintain minDiff from prev
        long target = prev + minDiff;
        // The adjusted value must be in [nums[i], nums[i] + d]
        if (target <= nums[i] + d) {
            // Assign the max between target and nums[i]
            prev = Math.max(target, nums[i]);
        } else {
            // Cannot maintain minDiff
            return false;
        }
    }
    return true;
}

```

[274. H-Index](https://leetcode.com/problems/h-index/)

```cpp
class Solution {
private:
    bool canFit(const vector<int>& citations, int h) {
        int count = 0;
        for (const int& n : citations) {
            if (n >= h) count++;
        }
        return count >= h;
    }

public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canFit(citations, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/binary-search/binary-search-to-split-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.