Introduction

The ternary search algorithm is a divide-and-conquer algorithm used for finding an element in a sorted array. It works by dividing the array into three parts instead of two, as in binary search, and recursively searching in the relevant section.

Program Structure

The program consists of the following main components:

• Function Declaration: A function named ternarySearch is defined to perform the search.
• Base Case: The search stops when the range is invalid or the element is found.
• Recursive Case: The function divides the array into three segments and determines in which segment to continue the search.
• Input/Output: The main function handles user input and output, printing the result of the search.

Code Implementation

#include 

// Function to perform ternary search
int ternarySearch(int arr[], int left, int right, int x) {
    if (right >= left) {
        // Finding the mid1 and mid2
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;

        // Check if the element is at mid1
        if (arr[mid1] == x) {
            return mid1;
        }
        // Check if the element is at mid2
        if (arr[mid2] == x) {
            return mid2;
        }
        // If the element is smaller than mid1, search in the left third
        if (x < arr[mid1]) { return ternarySearch(arr, left, mid1 - 1, x); } // If the element is greater than mid2, search in the right third else if (x > arr[mid2]) {
            return ternarySearch(arr, mid2 + 1, right, x);
        }
        // If the element is in between mid1 and mid2, search in the middle third
        else {
            return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
        }
    }
    // Element is not present in the array
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 9; // Element to search for
    int result = ternarySearch(arr, 0, n - 1, x);

    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }
    return 0;
}

Conclusion

The ternary search algorithm is efficient for searching in sorted arrays and can be an interesting alternative to binary search. Its implementation is straightforward and follows the divide-and-conquer principle. However, it is worth noting that the performance difference between ternary search and binary search is often negligible in practical scenarios.