Searching is a key task in programming, especially when working with sorted arrays. While binary search splits the array into two halves, ternary search divides it into three parts, offering an alternative approach to find elements efficiently. This method can be particularly useful when you want to explore how dividing a problem into more parts can optimize the search.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search works by calculating two midpoints in a sorted array and checking the key against these points. Depending on the comparison, the search continues in one of the three segments. For beginners, ternary search is a great example of divide-and-conquer strategy, showing how careful partitioning can reduce the number of comparisons and speed up searching in sorted datasets.
Program 1: Iterative Ternary Search
This program demonstrates the iterative approach to ternary search, which avoids recursion and repeatedly reduces the search range.
#include <iostream>
using namespace std;
int ternarySearchIterative(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; // key not found
}
int main() {
int arr[] {10, 20, 30, 40, 50, 60, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 50;
int result = ternarySearchIterative(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}In this program, the array is divided into three parts using two midpoints. The algorithm checks both midpoints and narrows the search to the appropriate segment. Beginners can appreciate how this divide-and-conquer technique reduces the number of comparisons compared to linear search.
Program 2: Recursive Ternary Search
Recursion provides another approach, where the function repeatedly calls itself with updated boundaries until the key is found.
#include <iostream>
using namespace std;
int ternarySearchRecursive(int arr[], int left, int right, int key) {
if (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])
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);
}
return -1; // key not found
}
int main() {
int arr[] {5, 15, 25, 35, 45, 55, 65};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 35;
int result = ternarySearchRecursive(arr, 0, n - 1, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}This recursive approach emphasizes the divide-and-conquer nature of ternary search. By continually reducing the search space into thirds, beginners can see how recursion helps simplify complex search logic while keeping the code clean and readable.
Program 3: Ternary Search with User Input
This program allows the user to enter the key they want to search in a predefined sorted array, providing a more interactive learning experience.
#include <iostream>
using namespace std;
int ternarySearchInteractive(int arr[], int left, int right, int key) {
if (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])
return ternarySearchInteractive(arr, left, mid1 - 1, key);
else if (key > arr[mid2])
return ternarySearchInteractive(arr, mid2 + 1, right, key);
else
return ternarySearchInteractive(arr, mid1 + 1, mid2 - 1, key);
}
return -1;
}
int main() {
int arr[] {2, 4, 6, 8, 10, 12, 14, 16};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Enter the element to search: ";
cin >> key;
int result = ternarySearchInteractive(arr, 0, n - 1, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}This interactive version allows beginners to experiment with different inputs and observe how ternary search splits the array and searches within the correct segment.
Frequently Asked Questions (FAQ)
Here are some common beginner questions about ternary search:
Q1: What is ternary search?
Ternary Search is a search algorithm that divides the array into three parts and searches for the target element by comparing it with two midpoints.
Q2: When is ternary search better than binary search?
Ternary search can reduce the number of comparisons slightly compared to binary search for very large arrays, but in practice, binary search is often faster due to fewer operations per step.
Q3: Can ternary search work on unsorted arrays?
No, the array must be sorted for ternary search to work correctly.
Q4: What is the time complexity of ternary search?
The time complexity is O(log₃ n), which is similar to binary search’s O(logâ‚‚ n).
Q5: Should beginners focus on ternary or binary search?
Binary search is easier and more widely used, but ternary search is a good way to learn advanced divide-and-conquer strategies.
Conclusion
Ternary Search is a divide-and-conquer searching algorithm that splits a sorted array into three segments. In this article, we explored iterative, recursive, and interactive implementations in C++, showing beginners how to efficiently narrow down the search space.
By practicing ternary search, beginners can understand how dividing a problem into multiple parts can improve algorithm efficiency and develop a stronger foundation in search algorithms. It also prepares learners for more complex algorithmic thinking and real-world problem solving in programming.
