There exists a recursive solution for the binary search algorithm. At each step lower and higher bounds for the search interval are updated and the search key is scanned in this new updated interval.
For recursive binary search implementation; search interval is updated depending on the midPoint value.
midPoint = lowerBound+(higherBound-lowerBound)/2
For the starting step; lowerBound is 0 and higherBound is the last array index.
Following sample project created by qt creator and contains following files:
1- SearchIntArrayRecursively.pro
2- main.cpp
SearchIntArrayRecursively.pro file contains project configuration.
TEMPLATE = app
CONFIG += console
CONFIG -= app_bundle
CONFIG -= qt
SOURCES += main.cpp
main.cpp file contains main method and recursive binarySearch function implementations.
#include <stdio.h>
int getIndexOfItemRecursively(int pSearchedItem, int* pArray, int mLowerBound, int mHigherBound)
{
if( mLowerBound > mHigherBound )
return -1;
int midIndex = mLowerBound+(mHigherBound-mLowerBound)/2;
if( pSearchedItem < pArray[midIndex] )
return getIndexOfItemRecursively(pSearchedItem, pArray, mLowerBound, midIndex-1);
else if(pSearchedItem>pArray[midIndex])
return getIndexOfItemRecursively(pSearchedItem, pArray, midIndex+1, mHigherBound );
else
return midIndex;
}
int findIndexOfItem( int pSearchedItem, int* pArray, int pTotalItemCount )
{
return getIndexOfItemRecursively(pSearchedItem, pArray, 0, pTotalItemCount-1);
}
int main(int argc, char* argv[])
{
int mArray[] = {1, 2, 4, 12, 34, 45, 56, 67, 78, 89, 90};
int mLengthOfArray = sizeof(mArray)/sizeof(int);
printf("There are %d items in the array\n", mLengthOfArray);
printf("Items :\n");
for(int i = 0; i<mLengthOfArray; i++)
{
if( i!=mLengthOfArray-1 )
printf("%d,", mArray[i]);
else
printf("%d\n", mArray[i]);
}
printf("Indexes :\n");
for(int i = 0; i<mLengthOfArray; i++)
{
if( i!=mLengthOfArray-1 )
printf("%d,", i);
else
printf("%d\n\n", i);
}
int mSearchItem = 12;
int mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
if( mIndex!=-1 )
printf("Item %d is at index %d\n", mSearchItem, mIndex);
else
printf("Item %d not found in the array\n",mSearchItem);
mSearchItem = 89;
mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
if( mIndex!=-1 )
printf("Item %d is at index %d\n", mSearchItem, mIndex);
else
printf("Item %d not found in the array\n",mSearchItem);
mSearchItem = 91;
mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
if( mIndex!=-1 )
printf("Item %d is at index %d\n", mSearchItem, mIndex);
else
printf("Item %d not found in the array\n",mSearchItem);
return 0;
}
We can analyze the steps for the first search item 12.
Search for 12
:
Find midPoint. For this case
midPoint is at index 5. If the
searchItem (12) is less than the item at index midPoint (45) then
update higherBound value with midpoint-1.
Search in the new range with
new higherBound value. higherBound is now midPoint-1. And lowerBound
is 0.
New Sub Array Shrinks To 5 Items:
Find midPoint. For this case
midPoint is at index 2. If the searchItem is higher than the item at
index midPoint then update lowerBound value with midpoint+1.
Search in the new range with
new lowerBound value. lowerBound is now midpoint+1 and higherBound
does not change for this case.
New Sub Array Shrinks To 2 Items :
Find midPoint. For this case
midPoint is at index 3.
SearchedItem is not less than
the item at midPoint.
SearchedItem is not higher than
the item at midPoint.
Then item is at midPoint.
Return index of midPoint.
When you run the above recursive binary search sample following console output is generated :
