Binary Search Sorted Int Array Recursively

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 :