Binary Search

Binary Search

Try out this game before Beginning,

https://www.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/a-guessing-game

Well you must have thought of some strategy to find the number in optimal way.

Iterating through all the numbers is not possible with the given constraints.

Let’s look at one of the Strategy( I guess only one thats intuitive ;P)

At its most fundamental level, a Binary search is employed to find a value in a sorted sequence.

Eg:- An array of real integers.

Binary_Search(A, value):

beg=1 , end = A.size

While beg <= end:

Mid = floor((beg+end)/2)

If A[mid] == value :

Return mid; // Return the position of the value

Else if A[mid] < value :

beg=mid+1;  // Search the upper half of the array

Else

end=mid-1;  // Search the lower half of the array    

Return -1;      // Indicates target not found

If you analyze the pseudo code properly, you will realize that at each execution of the loop

the array to search becomes half, making the time complexity O(logN). This means that

even if the array is of the size 10^7, you can find the value in 25 executions.

Let’s take the example of the following sorted array (value in brackets indicate the index)

-1029(1) -786(2) -81(3) -23(4) 0(5) 1(6) 9(7) 45(8) 1098(9) 5467(10) 10291(11) 12991(12) 90992(13) 290311(14)

We have to find the value -23.

Initially:-

beg=1, end=14

Step 1:-

Mid = 7

A[mid]=9

Thus, A[mid] > value

So, end=6

Step 2:-

Mid=3

A[mid]=-81

Thus, A[mid]<value

So, beg=4

Step 3:-

Mid=5

A[mid]=0

Thus, A[mid]>value

So, end=4

Step 4:-

Mid=4

A[mid]=-23

Bingo, we found the value

Note how the range becomes shorter and shorter after each execution! This is what makes binary search very
powerful.

If we had to search for an element that is not there, the range would become shorter and shorter till 1,

after which it comes out of the loop and returns -1.

STL Functions for binary search

STL offers functions to implement binary search in an efficient way. Try exploring the functions binary_search(),
lower_bound(), upper_bound().

Expanding Further

Now, binary search can do way more things than just find a value in an array of integers. It can be used wherever
there is a monotonous function that has either a true or a false value.

Let’s suppose f(x) is a boolean function which returns either true or false. In a problem, you encounter such a function.
Now you want to test whether binary search is applicable or not. What is the required condition?

In simple terms, a binary search can be used whenever a predicate function (a yes or no function) is monotonous (i.e)  

has a series of yes followed by a series of no or the vice-versa. In this case, binary search can be used to determine
where the transition takes place. This comes quite handy.

Eg:- The following is the output of f(x) (x is in the bracket).

Yes(1) Yes(2) Yes(3) No(4) No(5) No(6) No(7) No(8) No(9) No(10)

Now, you want to determine the max value of x for which f(x) gives Yes. You can employ the following pseudo-code.

Abstract_binary_search(up)  // upper limit to search

beg=1, end=up

While beg<=end:

Mid = floor((beg+end)/2)

If f(mid) = true:   // f(x) is the predicate function.

beg=mid+1

Else:

end=mid-1

Return end  // returns the last value for which f(x) is Yes

Let’s analyze what is happening.

Initially:-

beg=1, end=10

Step 1:-

Mid = 5

f(mid)=No

So, end=4

Step 2:-

Mid=2

f(mid)=Yes

So, beg=3

Step 3:-

Mid=3

f(mid)=Yes

So, beg=4

Step 4:-

Mid=4

f(mid)=No

So, end=3

Now it breaks out of the loop. And beg points to the first No, and end points to the first Yes.

As you can see, since this is a function, this binary search doesn’t require an array or sequence
of integers and hence is not limited by memory space. Even a billion integers can be explored
in 30 steps, because of its O(logN) complexity.

This can be applied for a wide range of problems. Let’s take the example of Aggressive Cows .

The necessary thing to solve this question is proper observation & then working on how to
choose the predicate function so that we can apply binary search. Suppose X is the maximum possible separation between the cows.

Then for all j<X, it is possible to arrange the cows with that separation and for all j>X, it is
not possible to arrange the cows with that separation. This means that we can try to choose a monotonous function which might help us to solve the question with a binary search approach.

Now, if we choose F(x) such that it gives True, if it is possible to arrange the cows with at
least X distance between, and False otherwise, we have a series of Yes followed by No,
and we need to find the maximum value of the occurrence of Yes. Doesn’t this sound familiar?

Let’s take a look at the pseudo code.

f(A,dist,cows):

n=A.size

i=1

For j in 2...cows:

k=i+1

While k<=n and A[k]-A[i]<dist:

k=k+1

If k = n+1:

Return false

i=k

j=j+1

If j>cows:

Return true

Return false

Solve(A,cows):

n=A.size

sort(A)

beg=1,end=A[n]-A[1]

While beg<=end:

mid=floor((beg+end)/2)

If f(A,mid,cows) = true:

beg=mid+1

Else:

end=mid-1

Return end

The analysis of the pseudo code and its time complexity is left as an exercise for the reader.

PROBLEMS TO PRACTICE:

https://www.codechef.com/problems/SNAKEEAT

https://www.codechef.com/problems/STACKS

https://www.spoj.com/problems/SUBS/

https://www.codechef.com/problems/FORESTGA

https://www.interviewbit.com/courses/programming/topics/binary-search/

https://www.codechef.com/IOITC181/problems/CIRCINTE

You should definitely go through this for some more detailed insights:

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search