Can someone please explain me the scenario where and how can I know if the binary search is applicable or not if the problem has indirect application of Binary Search?
How can I know if a problem can be done using Binary Search?
The search space, etc the variations of binary search.
@raghav6 While applying Binary Search, you first need to identify that the problem is to be solved by binary search. To identify this, you need :
- A Variable : you need a variable on which you can apply the binary search, i.e. it can range from “beg=0 and end=INT_MAX/large value”.(span is formed from beg to end)This variable acts as the mediator for the problem to reach a solution.
- A comparison function : you need a comparison function which makes “computation” and returns result so that the answer is reached or the values of “beg or end” can be changed (i.e. : beg=mid+1 or end = mid -1)
In Book Allocation Problem:
variable : Number of pages allotted
function : given number of pages( i,e. “mid”) gives a correct allocation such that each person gets at least mid amount of pages and each book is used.
In Painter Problem:
variable: Number of blocks allotted
function: Each painter is allotted “mid” length of boards and each board is used
In Aggressive cows:
variable: min distance between cows
function: “mid” distance should be between the barns.
Now consider the book allocation problem. I assume that you have read the question and you are familiar with it.In this problem, we have to minimize the maximum number of pages each student has to read.
Note that whenever there are such optimization problem where you have to maximize/minimize and the span of final answers form a monotonic function, Binary Search approach can be applied.
Consider sample case: where there are 4 books and 2 student
Pages in each book: 10 20 30 40 Here answer is 60.(1 student allotted 10+20+30 pages and other 40 pages)
Here the span of answers will be from 0 to 10+20+30+40=100 as a student can read a maximum of 100 pages.You answer will lie in this span and you have to optimize it. We say that the span of answers form a monotonic function because answer<60 is not possible(for which isValid function will return false) and answer>60 is always possible(for which isValid function will return true).Least among all true values(ie.60) is the answer for which we apply binary search:
So,
IsValid function returns false only when the number of students computed in it is greater than the given number of students.
IsValid function returns true when the number of students computed <=the given number of students.
Refer this video to understand well https://youtu.be/TC6snf6KPdE
Hope this help.
