Binary Search Based : Ship packages

Binary search based problem : Ship all the packages with given weights in N days with a criteria.

Criteria 1 : Ship all the packages.
Criteria 2 : Ship the packages in continuous order.
Criteria 3 : Ship the packages in N days choosing the ship with minimum capacity.

Reference : LeetCode Problem Ship Packages

Binary Search looks for a value in a sorted array. It compares the middle number of the array with the searched value. If the middle number equals the searched value, the position of the middle number is returned. If the middle number is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched using binary search.

Time complexity of the binary search algorithm for finding the smallest number in a sorted rotated array : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?

C++ : Binary search use case : Ship all the packages with given weights in N days with a criteria. Implemented in C++11

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

bool CanShip(vector<int>& weights, int max_capacity, int days) {
    
    int current_capacity = 0;
    int day_num = 1;

    for (const auto& w : weights) {
        current_capacity += w;

        /* Current weight allotment exceeds the max_capacity, so this
           weight may go on the ship the next day. */
        if (current_capacity > max_capacity) {
            current_capacity = w;

            /* Check if this weight can never go on any ship */
            if (current_capacity > max_capacity)
                return false;

            day_num++;
        }    
    }   
    if (day_num <= days)
        return true;
    return false;
}

int ShipWithinDays(vector<int>& weights, int days) {

    int beg = 0;
    int end = INT_MAX;
    int possible_capacity = -1; 

    if (weights.size() == 0)
        return 0;

    if (weights.size() == days)
        return *max_element(weights.begin(), weights.end());

    while(beg <= end) {

        int max_capacity = beg + (end-beg)/2;

        if (CanShip(weights, max_capacity, days)) {
            possible_capacity = max_capacity;
            end = max_capacity - 1;
        } else {
            beg = max_capacity + 1;
        }
    }   
    return possible_capacity;
}

int main() {

    vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int days = 5;

    cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
    days = 1;
    cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
    days = 2;
    cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
    return 0;
}

Output

Minimum capacity of ship for 5 days : 15
Minimum capacity of ship for 1 days : 55
Minimum capacity of ship for 2 days : 28

Copyright (c) 2020, Algotree.org.
All rights reserved.