Searching efficiently in a sorted array is an essential skill for any programmer. While Binary Search divides the array into two halves, Ternary Search takes it a step further by dividing the array into three parts. This allows for faster convergence on the target element in certain cases. The concept is simple yet powerful, and learning it helps beginners understand how recursive or divide-and-conquer algorithms work.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is mostly used when dealing with large, sorted datasets. It is a stepping stone for understanding more advanced searching and optimization algorithms. By learning Ternary Search, you also develop intuition for breaking problems into smaller segments efficiently, which is a fundamental skill in programming.
Program 1: Ternary Search Using Loop
This program demonstrates a basic loop-based Ternary Search. It divides the array into three parts, compares the target with two midpoints, and continues the search in the correct segment.
using System;
class Program
{
static int TernarySearch(int[] arr, int key)
{
int left = 0;
int right = arr.Length - 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;
}
static void Main()
{
int[] numbers = { 1, 4, 7, 10, 13, 16, 19 };
int target = 13;
int result = TernarySearch(numbers, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This loop-based approach is ideal for beginners to visualize the segmenting process. It clearly shows how dividing the array into three parts reduces search space faster than Linear Search.
Program 2: Ternary Search Using Recursion
Recursion makes the Ternary Search elegant by handling the array divisions automatically. This approach is ideal for understanding divide-and-conquer principles.
using System;
class Program
{
static int TernarySearchRecursive(int[] arr, int left, int right, int key)
{
if (left > right)
return -1;
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);
}
static void Main()
{
int[] numbers = { 2, 5, 8, 11, 14, 17, 20 };
int target = 14;
int result = TernarySearchRecursive(numbers, 0, numbers.Length - 1, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}The recursive approach emphasizes breaking problems into smaller chunks. It is particularly useful when the algorithm is applied repeatedly to different segments of the array.
Program 3: Ternary Search for Floating Numbers
Ternary Search can also work on sorted floating-point numbers, which is useful in applications like numerical optimization.
using System;
class Program
{
static int TernarySearchFloat(double[] arr, double key)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (Math.Abs(arr[mid1] - key) < 1e-9)
return mid1;
if (Math.Abs(arr[mid2] - key) < 1e-9)
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;
}
static void Main()
{
double[] numbers = { 1.1, 2.3, 3.5, 4.7, 5.9 };
double target = 4.7;
int result = TernarySearchFloat(numbers, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This example demonstrates adaptability. Beginners learn how Ternary Search can be applied beyond integers.
Program 4: Ternary Search on String Arrays
Ternary Search can also be applied to sorted string arrays, such as names or IDs.
using System;
class Program
{
static int TernarySearchString(string[] arr, string key)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
int cmp1 = string.Compare(arr[mid1], key);
int cmp2 = string.Compare(arr[mid2], key);
if (cmp1 == 0)
return mid1;
if (cmp2 == 0)
return mid2;
if (cmp1 > 0)
right = mid1 - 1;
else if (cmp2 < 0)
left = mid2 + 1;
else
{
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1;
}
static void Main()
{
string[] names = { "Alice", "Bob", "Charlie", "Diana", "Edward" };
string target = "Charlie";
int result = TernarySearchString(names, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This program shows how Ternary Search works with lexicographical ordering, which is common in text-based data.
Frequently Asked Questions (FAQ)
Q1: When should I use Ternary Search?
Ternary Search is best for large, sorted arrays or when a problem requires divide-and-conquer.
Q2: Can Ternary Search replace Binary Search?
Not always. Binary Search is simpler and often more efficient in practice, but Ternary Search teaches multi-way splitting concepts.
Q3: What is the time complexity of Ternary Search?
The time complexity is O(log3 n), which is slightly better than Binary Search in theory, though constants may affect real-world performance.
Q4: Is Ternary Search only for numbers?
No. It works for strings, floats, or any sortable data type as long as the array is sorted.
Conclusion
Ternary Search is a powerful algorithm for sorted datasets. By dividing the search space into three parts, it efficiently reduces the number of comparisons. Beginners can learn a lot about recursion, divide-and-conquer strategies, and adaptability across data types.
Practicing Ternary Search with integers, floats, strings, and recursion helps build confidence in algorithmic thinking. Once comfortable, exploring Jump Search, Interpolation Search, and Exponential Search will further enhance your searching skills.
