Criteria 1 : Allot all the books.

Criteria 2 : Allot the books in continuous order.

Criteria 3 : Allot the books such that the maximum number of pages of books issued to a student is minimum.

**Reference :** Interview Bit Problem Allot Books

**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 : Allotting all the library books to N student with a criteria. Implemented in C++11**

```
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
bool CanAllocate(vector<int>& books, int& maxpages, int students) {
int student_num = 1;
int allocated_pages = 0;
for (const auto& pages : books) {
if (allocated_pages <= maxpages) {
allocated_pages += pages;
/* Current allocation exceeds the maxpages, so this
allocation may go to the next student.*/
if (allocated_pages > maxpages) {
allocated_pages = pages;
/* The allocation of allocated_pages > maxpages being invalid cannot be done for any student */
if (allocated_pages > maxpages)
return false;
student_num++;
}
}
}
/* If student number is less than total student, more pages have got allocated to
the students. We can start with less number of pages in the next go.
So continue the binary search */
if (student_num <= students)
return true;
return false;
}
int IssueBooks(vector<int>& books, int students) {
if (books.size() == 0)
return 0;
if (books.size() == students)
return *max_element(books.begin(), books.end());
int end = INT_MAX;
int beg = 0;
int possible_pages = 0;
while (beg <= end) {
int maxpages = beg + (end - beg)/2;
if (CanAllocate(books, maxpages, students)) {
possible_pages = maxpages;
end = maxpages - 1;
} else {
beg = maxpages + 1;
}
}
return possible_pages;
}
int main() {
vector<int> books = {10, 32, 70, 88};
// Student(s) 1 1:(10 + 32 + 70 + 88)
// Student(s) 2 1:(10 + 32 + 70), 2:(88)
// Student(s) 3 1:(10 + 32) 2:(70), 3:(88)
// Student(s) 4 1:(10), 2:(32), 3:(70), 4:(88)
int students = 1;
cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students) << endl;
students = 2;
cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students) << endl;
students = 3;
cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students) << endl;
students = 4;
cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students) << endl;
return 0;
}
```

Output

```
Maximum possible pages allocated to 1 : 200
Maximum possible pages allocated to 2 : 112
Maximum possible pages allocated to 3 : 88
Maximum possible pages allocated to 4 : 88
```

All rights reserved.