Ternary Search in C++

The Ternary Search is a divide and conquer algorithm, very similar to binary search. It can find a value in a sorted array, by slitting the array into 3 parts. The binary search divides the array in 2 parts. We compare the search value with the 2 middle points that we determine, and, in this way, we can know in which third of the array the value is situated. After this we apply the algorithm again, splitting the remaining array into 3 parts. We repeat this operation until we find the desired value in the array.

// Ternary Search

#include <iostream>
using namespace std;

int ternarySearch(int arrayOfNumbers[], int searchForNumber, int leftIndex, int rightIndex)
{
    if (rightIndex >= leftIndex) {

        // Find the 2 middle indexes
        int middle1 = leftIndex + (rightIndex - leftIndex) / 3;
        int middle2 = rightIndex - (rightIndex - leftIndex) / 3;

        // See if the value searched for equals one of the 2 middle points
        if (arrayOfNumbers[middle1] == searchForNumber)
        {
            printf("The number %d is found at index %d", searchForNumber, middle1);
            return middle1;
        }
        if (arrayOfNumbers[middle2] == searchForNumber)
        {
            printf("The number %d is found at index %d", searchForNumber, middle2);
            return middle2;
        }

        // Find the third of the array where the searched value is
        if (searchForNumber < arrayOfNumbers[middle1])
        {
            return ternarySearch(arrayOfNumbers, searchForNumber, leftIndex, middle1 - 1);
        }
        else if (searchForNumber > arrayOfNumbers[middle2])
        {
            return ternarySearch(arrayOfNumbers, searchForNumber, middle2 + 1, rightIndex);
        }
        else
        {
            return ternarySearch(arrayOfNumbers, searchForNumber, middle1 + 1, middle2 - 1);
        }
    }

    printf("The number %d was not found in the array", searchForNumber);
    return -1;
}

int main()
{
    int arrayOfNumbers[] = {1, 6, 9, 15, 17, 21, 30, 48, 61, 99};
    int searchForNumber = 21;
    int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);

    int leftIndex = 0;
    int rightIndex = numberOfElements - 1;

    int result = ternarySearch(arrayOfNumbers, searchForNumber, leftIndex, rightIndex);
}