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 ?

Integer range is -2,147,483,648 to 2,147,483,647. If you are searching in an array of size 2,000,000,000 and the number searched for is located at index 1,999,999,999. When you search in the upper half of array, beg=1,000,000,001 and end=2,000,000,000. If mid is calculated as (low+high)/2, low+high = 3,000,000,001; which exceeds the range of int, resulting in overflow errors. But mid calculated as beg + (end-beg) = 1,000,000,001 + 999,999,999 = 2,000,000,000; which fits in the integer range.

**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
```

All rights reserved.