Binary Search Application

#1

Can’t Able to get where exactly the Binary Search use when it comes to these Book Allocation Problem,Painter,Aggressive Cows.

#2

Hey,
While applying Binary Search, you first need to identify that the problem is to be solved by binary seach. To identify this, you need :

  1. 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”. This variable acts as the mediator for the problem to reach a solution.
  2. A comparision function : you need a comparision 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 alloted
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 alloted
function: Each painter is alloted “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.

You can refer to the codes by googling each of them and then compare with the above infrences.

Also, this tutorial might be very useful to you; TOPCODER

1 Like
#3

Which particular type of Questions need to be Solved using binary Search.

#4

here is playlist by prateek sir

#5

Thank you Bhaiya for the Explanation.

1 Like