binarysearch

• Check if search space is monotonic
• Check if we can eliminate search space by half based on some decision

1011. Capacity To Ship Packages Within D Days

• Our search space (capacity) is the range [max weight, sum of all weights]
• If our current capacity is too small, then all smaller capacities are small too. So, we ELIMINATE the SEARCH SPACE by half.
• The func daysTaken(capacity) is montonic - days decrease as capacity increases - thus we can eliminate search spaces using Binary Search

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int l = max(weights), r = sum(weights);
      
        while(l < r){
            int mid = l + (r-l) / 2;
            if(daysTaken(mid, weights) > days) 
                l = mid + 1;    // capacity too low
            else
                r = mid; 
        }
        return r;
    }
    private int daysTaken(int capacity, int[] weights){
        int sum = 0, days = 1;
        for(int w: weights){
            if(sum + w > capacity){ // current ship is filled
                sum = 0;
                days++;
            }
            sum += w;
        }
        return days;
    }
}