Bike Racers
Binary Search
Binary search is the most prominent example of a Divide and Conquer algorithm.
Suppose you are given an array of size in sorted order and you have to return the index of an element.
Basic algorithm is
initialize low = 0, high = N, mid = (low + high)/2
check if element is at position mid; if found, return
else depending upon value of mid is lower or greater, we explore the right side of the array or the left side
Sample recursive function code in C++:
int binary_search(int A[], int key, int imin, int imax)
{
// test if array is empty
if (imax < imin)
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);
// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid - 1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid + 1, imax);
else
// key has been found
return imid;
}
}
Sample iterative solution in C++:
int binary_search(int A[],int N,int key){
// considering 1 based index
int low , high , mid ;
low = 1 ;
high = N ;
while(low <= high){
mid = (low + high)/2 ;
if(A[mid] == key){
return mid ; // a match is found
}else if(A[mid] < key){ // if middle element is less than the key
low = mid + 1 ; // key will be right part if it exists
}else{
high = mid - 1 ; // otherwise key will be in left part if it exists
}
}
return -1 ; // indicating no such key exists
}
Common Variations of BinarySearch:
- LowerBound: find an element in a sorted array of intergers such that , where key is given.
- UpperBound: find an element in a sorted array of intergers such that , where key is given.
UpperBound Implementation in C++:
int UpperBound(int A[],int N,int K){
int low , high , mid ;
low = 1 ;
high = N ;
while(low <= high){
mid = ( low + high ) / 2 ; // finding middle element
if(A[mid] > K && ( mid == 1 || A[mid-1] <= K )) // checking conditions for upperbound
return mid ;
else if(A[mid] > K) // answer should be in left part
high = mid - 1 ;
else // answer should in right part if it exists
low = mid + 1 ;
}
return mid ; // this will execute when there is no element in the given array which > K
}
LowerBound Implementation in C++:
int LowerBound(int A[],int N,int K){
int low , high , mid ;
low = 1 ;
high = N ;
while(low <= high){
mid = ( low + high ) / 2 ; // finding middle element
if(A[mid] >= K && ( mid == 1 || A[mid-1] < K )) // checking conditions for lowerbound
return mid ;
else if(A[mid] >= K) // answer should be in left part
high = mid - 1 ;
else // answer should in right part if it exists
low = mid + 1 ;
}
return mid ; // this will execute when there is no element in the given array which >= K
}
NOTE : C++ STL (Standard Template Library) already contains implementation of all of these functions. Check out here for additional knowledge binarysearch, lowerbound, upperbound
Related challenge for Binary Search