Tutorial fo

Binary search

Binary search involves dividing the search space by 2 in each iteration to finally arrive at a very small and trivial space.

Binary Search in an array

Consider a sorted array A[1... n ] with n-elements. Now we want to find the position of a number x within this array. We can do this using binary search with a complexity of O( log n ).

Algorithm

Iterative binary search

binary_search( A[1..n], v )
{
    lo := 1
    hi := n
    while( lo <= hi )
    {
        mid := (lo+hi)/2
        if( a[mid] == v )
            return true;
        if( a[mid] > v )
            hi = mid-1;
        else
            lo = mid+1;
    }
    return false;
}

Recursive binary search

binary_search( A[1..n], v, lo, hi )
{

mid := (lo+hi)/2
if( a[mid] == v )
return true;
if( lo >= hi )
return false;
if( a[mid] > v )
return binary_search( A, v, lo, mid-1 );
else
return binary_search( A, v, mid+1, hi );

}

Inbuilt-binary search

C++

C++ has 3 functions that are a part of the <algorithms> and are part of the std namespace.

They are binary_search, lower_bound, upper_bound

To search in an array a with n-elements we can use this

[code]binary_search( a, a+n, v )[/code]

where v is the value we are searching for.

binary_search returns a boolean value, telling if the value v exists or not.

lower_bound and upper_bound return the pointer locations where the value might be present.

Lower bound returns the i-th location in the array where the either i-1 < 0 or a[i-1] < v

Upper bound returns the i-th location in the array where either i is n or a[i] <= v

For e.g.

consider this array

1 2 2 3 3 3 3 5 7 7

we are searching for value 3

1 2 2 3 3 3 3 5 7 7

The lower position 3 is returned by lower bound and the upper one by upper bound.

We can similary use this on vectors, but lower bound and upper bound would return iterators instead of pointers.

Problems involving binary search in an array.

http://www.spoj.pl/problems/ABCDEF

http://www.spoj.pl/problems/NOTATRI

http://www.spoj.pl/problems/SCALE

http://www.spoj.pl/problems/SUMFOUR

http://www.spoj.pl/problems/SUBSUMS

http://www.spoj.pl/problems/ANARC05B

http://www.spoj.pl/problems/RENT

Binary search on functions

Consider an increasing function f(x). Now if we are given a value y of f(x) and we wish to compute the root x of this value, then we can use binary search to compute it. However in practice Newton-Raphson and interpolation search are much better and come closer to the real root in much fewer iterations. However there are many more interesting applications of binary search other than on purely “mathematical“ functions.

Let us begin then. Consider a function f(x) which is increasing, examples of such functions are given below.

While these are not.

So how do we find an x if we are given a value of f(x).

The idea is pretty simple, however we must remember that we cannot get to the exact answer, but an approximate one. However we can define the precision to which we get close to the exact answer. Also, due to the nature of real numbers on computers, we use some slight modifications and avoid using pseudo-code. The following is the C++ implementation to find the root of any increasing function f(x)

double f( double x )
{

	//do something and solve
}

//basically this means inverse function
of x, but we must remember that f(x) is increasing

double f_inverse( double y )
{

	double lo = 0, hi = 1e30; //or choose
a higher value if the final answer may exceed 10^30

	//While the difference from the actual
root is not acceptable, or accurate enough

	while( fabs( lo-hi ) > 1e-9 )

	{

		double mid = (lo+hi)/2;

		if( f( mid ) < y )

			lo = mid;

		else

			hi = mid;

	}

	return  (lo+mid)/2;
}

Similary we can also use binary to evalute decreasing functions.

Exercise :

Solve the following problems to get a hang of using binary search

Given integers a and b ( a, b <= 2*10⁹ )

Find a real number x such that x^a = b

You cannot use any inbuilt math libraries to solve this.

Find the smallest number n such that factorial n has exactly k-digits, or report that no such number exists ( Note that you will be working with discrete integers and not real numbers here )

Problems to practice

http://www.spoj.pl/problems/PIE

You can try to solve these problems which are hard versions of binary search

http://www.spoj.pl/problems/MKUHAR

http://www.spoj.pl/problems/SVADA

http://www.spoj.pl/problems/SUBS