
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 ).
A Tutorial and C Program for simple Binary Search in an Array : http://www.thelearningpoint.net/computer-science/arrays-and-searching-bi...
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*109 )
Find a real number x such that xa = 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
