C Exercises: Find the position of a target value within a array using Ternary search

C Programming Searching and Sorting Algorithm: Exercise-5 with Solution

Write a C program to find the position of a target value within an array using ternary search.

From Wikipedia
A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function. A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two thirds. A ternary search is an example of a divide and conquer algorithm.
Algorithm

Let f(x) be a unimodal function on some interval [l; r]. Take any two points m₁ and m₂ in this segment: l < m₁ < m₂ < r. Then there are three possibilities:

• if f(m₁) < f(m₂), then the required maximum can not be located on the left side - [l; m₁]. It means that the maximum further makes sense to look only in the interval [m₁;r]
• if f(m₁) > f(m₂), that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side - [m₂; r], so go to the segment [l; m₂]
• if f(m₁) = f(m₂), then the search should be conducted in [m₁; m₂], but this case can be attributed to any of the previous two (in order to simplify the code). Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.

• m₁ = l + (r-l)/3
• m₂ = r - (r-l)/3

Sample Solution:

Sample C Code:

#Source:https://bit.ly/3oJh12d
# include <stdio.h>
// Function to perform ternary search in a sorted array
int ternarySearch(int l, int array_size, int key, int array_nums[])
{
    // Continue search until the search space is valid
    while (array_size >= l) {
        // Find the mid1 and mid2 points for ternary search
        int mid1 = l + (array_size - l) / 3;
        int mid2 = array_size - (array_size - l) / 3;
        // Check if the key is present at any mid point
        if (array_nums[mid1] == key) {
            return mid1;
        }
        if (array_nums[mid2] == key) {
            return mid2;
        }
        // Determine in which region the key is present and adjust the search space accordingly
        if (key < array_nums[mid1]) {
            // The key lies in between l and mid1
            array_size = mid1 - 1;
        }
        else if (key > array_nums[mid2]) {
            // The key lies in between mid2 and array_size
            l = mid2 + 1;
        }
        else {
            // The key lies in between mid1 and mid2
            l = mid1 + 1;
            array_size = mid2 - 1;
        }
    }
    // Key not found
    return -1;
}
// Main function
int main()
{
    int n;
    int l = 0;
    // Sorted array for ternary search
    int array_nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    size_t array_size = sizeof(array_nums) / sizeof(int);
    // Print the original array
    printf("Original Array %d: ", array_size);
    for (int i = 0; i < array_size; i++) 
        printf("%d ", array_nums[i]);   
    printf("\n");
    // Input a number to search
    printf("Input a number to search: ");
    scanf("%d", &n);
    // Perform ternary search and print the result position
    int result_position = ternarySearch(l, array_size, n, array_nums);
    printf("\nElement found at position: %d", result_position);
    // Return 0 to indicate successful execution
    return 0;
}

Sample Output:

Original Array 10: 1 2 3 4 5 6 7 8 9 10
Input a number to search: 8

Element found at position: 7
--------------------------------
Process exited after 5.256 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program to find the position of a target value within a array using Linear search.
Next: C Array Exercises Home