Discrete Binary Search ( SPOJ AGGRESSIVE COWS)
We all know the standard Binary Search and it's working, let's explore some non-trivial applications of Binary Search and see the Real Power of Binary Search in this post. Discrete Binary Search : - Before proceeding any further I would request you all to read the famous SPOJ problem AGGRCOW . And try to think in terms of standard binary search on how can it be solved. If you got the solution, bingo you know what Discrete Binary Search is and can directly proceed to solve a similar question at the end of this post. If not, let's first learn what is Discrete Binary Search. Basically, assume that You have a function f(x) which is monotonically increasing (decreasing) on the interval [a, b]. f(a) < C < f(b) You want to find x such that f(x) = C. Then you can use binary search to find x. Essentially, you half the possible interval for the variable x each time. For the AGGRCOW question let's check for the test case, 1 5 3 1...