The Ternary Search algorithm is a divide-and-conquer search algorithm that can be used to find the position of a target value within a sorted array. Unlike binary search, which divides the array into two halves, ternary search divides it into three parts.

Program Structure

The program consists of the following key components:

• Function Definition: The main function of the algorithm is ternarySearch, which takes an array, its left and right bounds, and the target value as arguments.
• Recursive Search: The function recursively divides the array into three segments until the target value is found or the search space is exhausted.
• Main Function: The main function initializes the array, calls the ternarySearch function, and prints the result.

C++ Code

#include <iostream>

using namespace std;

/**
 * Ternary Search function.
 * @param arr The sorted array in which to search.
 * @param left The starting index of the search.
 * @param right The ending index of the search.
 * @param x The target value to find.
 * @return The index of the target value or -1 if not found.
 */
int ternarySearch(int arr[], int left, int right, int x) {
    if (right >= left) {
        // Calculate the two mid points
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;

        // Check if the target is at one of the mid points
        if (arr[mid1] == x) return mid1;
        if (arr[mid2] == x) return mid2;

        // Determine which segment to search in
        if (x < arr[mid1]) { return ternarySearch(arr, left, mid1 - 1, x); } else if (x > arr[mid2]) {
            return ternarySearch(arr, mid2 + 1, right, x);
        } else {
            return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
        }
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 7; // Target value to search for
    int result = ternarySearch(arr, 0, size - 1, x);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found." << endl;
    }
    
    return 0;
}

How It Works

The algorithm operates as follows:

1. It calculates two mid points in the current segment of the array.
2. It checks if the target value is at either of the mid points.
3. If not, it determines which segment of the array the target value is likely to be in and recursively searches that segment.
4. This process continues until the target value is found or the search space is exhausted.

Time Complexity

The time complexity of the Ternary Search algorithm is O(log3 n), which is generally more efficient than linear search but less efficient than binary search in practice.

Conclusion

Ternary Search is an efficient algorithm for searching sorted arrays. Its divide-and-conquer approach allows for quick searches in certain scenarios, particularly when the size of the dataset is large.