Searching is one of the fundamental tasks in programming. When you have a sorted array and want to find a specific element efficiently, using a smart algorithm can save time and resources. One such method is Ternary Search, which is similar to Binary Search but splits the array into three parts instead of two. This approach allows the algorithm to reduce the search space faster in some cases and is a great example of divide-and-conquer strategy in action.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is particularly useful in applications where comparisons are expensive or when data is large and sorted. It demonstrates how dividing a problem into smaller segments can improve efficiency. For beginners learning C programming, implementing Ternary Search is a helpful exercise in understanding both recursion and iterative problem-solving while reinforcing the concept of efficient searching algorithms.
Program 1: Iterative Ternary Search
The first program demonstrates Ternary Search using an iterative approach, making it easy for beginners to understand the step-by-step logic of the algorithm.
#include <stdio.h>
int ternarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == key)
return mid1;
if (arr[mid2] == key)
return mid2;
if (key < arr[mid1])
right = mid1 - 1;
else if (key > arr[mid2])
left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
printf("Enter the element to search: ");
scanf("%d", &key);
int index = ternarySearch(arr, n, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found in the array\n", key);
return 0;
}In this program, the array is divided into three parts using two midpoints, mid1 and mid2. The algorithm checks if the key is at either midpoint. If not, it reduces the search space depending on whether the key is smaller than mid1, larger than mid2, or in between. Beginners will find this approach easy to follow because it clearly shows how the array is narrowed down step by step until the key is found or the search space is empty.
Program 2: Recursive Ternary Search
Ternary Search can also be implemented recursively, which provides a cleaner, elegant way to divide the array until the element is found.
#include <stdio.h>
int ternarySearchRecursive(int arr[], int left, int right, int key) {
if (left > right)
return -1; // Element not found
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == key)
return mid1;
if (arr[mid2] == key)
return mid2;
if (key < arr[mid1])
return ternarySearchRecursive(arr, left, mid1 - 1, key);
else if (key > arr[mid2])
return ternarySearchRecursive(arr, mid2 + 1, right, key);
else
return ternarySearchRecursive(arr, mid1 + 1, mid2 - 1, key);
}
int main() {
int arr[] = {5, 15, 25, 35, 45, 55, 65, 75, 85};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
printf("Enter the element to search: ");
scanf("%d", &key);
int index = ternarySearchRecursive(arr, 0, n - 1, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found in the array\n", key);
return 0;
}The recursive approach works by continuously dividing the array into three parts and calling the function on the relevant segment. Beginners can appreciate how recursion reduces the search space naturally, without using loops, and how each recursive call focuses on a smaller portion of the array. It’s a great way to practice divide-and-conquer techniques in programming.
Program 3: Ternary Search with Floating-Point Numbers
Ternary Search is not limited to integers; it can also work with floating-point numbers, provided the array is sorted. This example shows the flexibility of the algorithm.
#include <stdio.h>
int ternarySearchFloat(float arr[], int n, float key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == key)
return mid1;
if (arr[mid2] == key)
return mid2;
if (key < arr[mid1])
right = mid1 - 1;
else if (key > arr[mid2])
left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1;
}
int main() {
float arr[] = {1.1, 2.5, 3.8, 4.4, 5.9, 6.7, 7.2};
int n = sizeof(arr) / sizeof(arr[0]);
float key;
printf("Enter the element to search: ");
scanf("%f", &key);
int index = ternarySearchFloat(arr, n, key);
if (index != -1)
printf("Element %.2f found at index %d\n", key, index);
else
printf("Element %.2f not found in the array\n", key);
return 0;
}This floating-point version uses the same logic as the integer versions. The step of dividing the array into three parts and checking positions remains the same, demonstrating that Ternary Search is flexible across numeric types. Beginners can experiment with decimals to see how the algorithm works in real-world scenarios.
Frequently Asked Questions (FAQ)
Here are some common questions about Ternary Search:
What is the time complexity of Ternary Search?
Ternary Search has a time complexity of O(log₃ n), slightly better than Binary Search in theory, but the difference is small in practice due to extra comparisons.
Is Ternary Search better than Binary Search?
It depends on the use case. Ternary Search reduces the search space faster but involves more comparisons per iteration. Binary Search is usually simpler and slightly faster in practice for most scenarios.
Does Ternary Search require sorted arrays?
Yes, the array must be sorted, as the algorithm relies on comparing the key with ordered elements.
Can Ternary Search work with floating-point numbers?
Yes, as long as the array is sorted, the algorithm can be adapted for floating-point values.
Why split into three parts instead of two?
Dividing into three parts reduces the search space more aggressively in each step, which demonstrates an alternative divide-and-conquer strategy.
Conclusion
Ternary Search is a fascinating searching algorithm that extends the principles of Binary Search by dividing the array into three segments instead of two. By doing so, it shows how different strategies can improve efficiency in searching sorted data.
The examples — iterative, recursive, and floating-point — illustrate how Ternary Search can be applied in various scenarios. Beginners can practice both iterative and recursive methods to strengthen their understanding of divide-and-conquer algorithms, recursion, and efficient searching. By exploring Ternary Search, learners also gain deeper insights into algorithm design and optimization in C programming.
