Ternary search

Ternary search is a searching algorithm that divides an input array into three subarrays—an array of the first third, an array of the last third, and an array between these two areas. It needs to pick two indexes, which are called middleLeftIndex and middleRightIndex. These two indexes are calculated based on the first index and the last index of the input array.

Developing ternary search algorithm

Suppose we have an array as we have in a binary search, {3, 8, 11, 15, 16, 23, 28, 30, 32, 39, 42, 44, 47, 48, 50}, and want to search for a value of 16. The array contains 15 elements, so we will have the fifth index as the middle-left index (middleLeftIndex = 4), and ninth index as the middle-right index (middleRightIndex = 8). By using these two indexes, we can find the searched value in each area using the ternary search algorithm itself (recursive invocation). The code of a ternary search algorithm in C++ is as follows:

int TernarySearch(
    int arr[],
    int startIndex,
  ...