ternary search Algorithm
The ternary search algorithm is an advanced searching technique that aims to find the minimum or maximum value of a unimodal function or determine the position of a specific target value within a sorted array. The algorithm is based on the divide and conquer strategy, where it divides the search interval into three equal parts and subsequently evaluates the function at two intermediate points. By comparing the function values at these points, the algorithm narrows down the search interval to one of the three sub-intervals, which contains the desired minimum or maximum value.
The efficiency of the ternary search algorithm lies in its ability to discard a significant portion of the search interval with each iteration, thereby reducing the number of comparisons required to locate the target value. This results in a logarithmic time complexity of O(log3 N), where N represents the size of the search interval. Although the ternary search algorithm performs fewer iterations compared to the binary search algorithm, it requires evaluating the function at two points, which can make it less efficient than binary search in certain scenarios. Nevertheless, the ternary search algorithm is an effective approach for solving optimization problems and searching through large datasets with a unimodal structure.
#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d\n", key, p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d", key, p);
} 
