Binary Search

Obra: Hey Pearl! what are you doing?
Pearl: I am studying Binary search.
Obra: Tell me something about this
 Pearl:
Binary search: As compare to linear search, it quite fast.
Approach take the median of lower bound and upper bound ( LB+UB/2). compare it with an element. if the element is greater than median then search will take place in right else in left place.

Obra:
Can you help out me to solve this problem using binary search?
Pearl: let's try.
Obra:
Let's Think, a number of people need to examine a number of filing containers. The containers are not all of the same sizes and we are told for each container how many boxes it contains. We are asked to find an assignment such that each person gets a sequential series of containers to go through and that it minimises the maximum amount of boxes that a person would have to look through.

let's  Imagine that we have an unlimited number of people at our disposal. The crucial observation is that, for some number LIMIT, we can calculate the minimum number of people needed so that each person has to examine no more than LIMIT boxes (if this is possible). Let's see how we'd do that. Some person needs to examine the first container so we assign any person to it. But, since the containers must be assigned in sequential order (a person cannot examine containers 1 and 3 without examining 2 as well), it's always optimal to assign him to the second container as well, if this does not take him over the limit we introduced (LIMIT). If it would take him over the limit, we conclude that his work is done and assign a new person to the second container. We proceed in a similar manner until all the containers have been assigned and assert that we've used the minimum number of people possible, with the artificial limit we introduced. Note here that the number of people is inversely proportional to LIMIT: the higher we set our limit, the fewer people we will need.

Now, if you go back and carefully examine what we're asked for in the problem statement, you can see that we are really asked for the smallest LIMIT such that the number of people required is less than or equal to the number of people available. With that in mind, we're almost done, we just need to connect the dots and see how all of this fits in the frame we've laid out for solving problems using binary search.

With the problem rephrased to fit our needs better, we can now examine the predicate Can the workload be spread so that each person has to examine no more than x boxes, with the limited number of people available? We can use the described greedy algorithm to efficiently evaluate this predicate for any x. This concludes the first part of building a binary search solution, we now just have to prove that the condition in the main theorem is satisfied. But observe that increasing x actually relaxes the limit on the maximum workload, so we can only need the same number of people or fewer, not more. Thus, if the predicate says yes for some x, it will also say yes for all larger x.

 Solution:
int Solution( boxes, int people ) {
   int n = boxes.size();
   int Low = *Max_element( box );
   int Upper = accumulate( box, 0 );

   while ( Low < Upper ) {
      int x = Low + (Upper-Low)/2;

      int required = 1, current_Load = 0;
      for ( int i=0; i<n; ++i ) {
         if ( current_Load + boxes[i] <= x ) {
            // the current person can handle it
            current_Load += boxes[i];
         }
         else {
            // assign next person
            ++required;
            current_Load = boxes[i];             
         }
      }

      if ( required <= people )
         Upper = x;
      else
         Low = x+1;
   }

   return Low;
}