Ternary Search is a searching algorithm used for finding an element in a sorted array by dividing the search space into three parts instead of two, as in Binary Search. It repeatedly narrows down the interval by comparing the target value with two midpoints. This allows it to eliminate one-third of the array in each step, which can make it more efficient than linear search for large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners in Rust, Ternary Search is a great way to practice conditional statements, loops, and recursion while understanding the concept of dividing a problem into smaller parts. It’s often applied in optimization problems, searching in strictly increasing or decreasing sequences, and situations where the array is sorted and fast lookup is needed. Learning this algorithm also strengthens your understanding of how recursive and iterative approaches differ in implementation.
Program 1: Iterative Ternary Search on Integers
This program demonstrates Ternary Search using a loop on a sorted array of integers. It calculates two midpoints and reduces the search interval accordingly.
fn ternary_search_iterative(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len() - 1;
while left <= right {
let third = (right - left) / 3;
let mid1 = left + third;
let mid2 = right - third;
if arr[mid1] == target {
return Some(mid1);
}
if arr[mid2] == target {
return Some(mid2);
}
if target < arr[mid1] {
right = mid1 - 1;
} else if target > arr[mid2] {
left = mid2 + 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
None
}
fn main() {
let numbers = [10, 20, 30, 40, 50, 60, 70];
let target = 40;
println!("Array: {:?}", numbers);
match ternary_search_iterative(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This iterative approach uses midpoints to divide the array into three sections. Beginners can see how comparing the target with two midpoints reduces the search space faster than checking each element individually.
Program 2: Recursive Ternary Search on Integers
Recursion provides a clean way to implement Ternary Search by calling the function on smaller intervals until the element is found.
fn ternary_search_recursive(arr: &[i32], target: i32, left: usize, right: usize) -> Option<usize> {
if left > right {
return None;
}
let third = (right - left) / 3;
let mid1 = left + third;
let mid2 = right - third;
if arr[mid1] == target {
return Some(mid1);
}
if arr[mid2] == target {
return Some(mid2);
}
if target < arr[mid1] {
return ternary_search_recursive(arr, target, left, mid1 - 1);
} else if target > arr[mid2] {
return ternary_search_recursive(arr, target, mid2 + 1, right);
} else {
return ternary_search_recursive(arr, target, mid1 + 1, mid2 - 1);
}
}
fn main() {
let numbers = [5, 15, 25, 35, 45, 55, 65];
let target = 25;
println!("Array: {:?}", numbers);
match ternary_search_recursive(&numbers, target, 0, numbers.len() - 1) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Recursion helps beginners understand the divide-and-conquer concept. Each recursive call narrows the search interval, showing clearly how the algorithm splits the array into thirds.
Program 3: Ternary Search for Floating-Point Numbers
Ternary Search also works with floats, useful for finding values in sorted decimal arrays.
fn ternary_search_floats(arr: &[f64], target: f64, left: usize, right: usize) -> Option<usize> {
if left > right {
return None;
}
let third = (right - left) / 3;
let mid1 = left + third;
let mid2 = right - third;
if (arr[mid1] - target).abs() < std::f64::EPSILON {
return Some(mid1);
}
if (arr[mid2] - target).abs() < std::f64::EPSILON {
return Some(mid2);
}
if target < arr[mid1] {
return ternary_search_floats(arr, target, left, mid1 - 1);
} else if target > arr[mid2] {
return ternary_search_floats(arr, target, mid2 + 1, right);
} else {
return ternary_search_floats(arr, target, mid1 + 1, mid2 - 1);
}
}
fn main() {
let numbers = [1.1, 2.2, 3.3, 4.4, 5.5];
let target = 3.3;
println!("Array: {:?}", numbers);
match ternary_search_floats(&numbers, target, 0, numbers.len() - 1) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Handling floating-point comparisons with EPSILON avoids precision issues. Beginners learn how to adapt integer algorithms for decimals without losing accuracy.
Program 4: Iterative Ternary Search with Debug Prints
This version prints the midpoints and the current search interval to help visualize the algorithm’s progress.
fn ternary_search_debug(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len() - 1;
while left <= right {
let third = (right - left) / 3;
let mid1 = left + third;
let mid2 = right - third;
println!("Checking mid1: {} ({}) and mid2: {} ({})", mid1, arr[mid1], mid2, arr[mid2]);
if arr[mid1] == target {
return Some(mid1);
}
if arr[mid2] == target {
return Some(mid2);
}
if target < arr[mid1] {
right = mid1 - 1;
} else if target > arr[mid2] {
left = mid2 + 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
None
}
fn main() {
let numbers = [10, 20, 30, 40, 50, 60, 70];
let target = 50;
println!("Array: {:?}", numbers);
match ternary_search_debug(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Debug statements help beginners understand how the search space is divided and how comparisons are made in each iteration.
Program 5: Ternary Search with Early Exit Optimization
This version quickly exits if the target is outside the array bounds, improving efficiency.
fn ternary_search_early_exit(arr: &[i32], target: i32) -> Option<usize> {
if arr.is_empty() || target < arr[0] || target > arr[arr.len() - 1] {
return None;
}
let mut left = 0;
let mut right = arr.len() - 1;
while left <= right {
let third = (right - left) / 3;
let mid1 = left + third;
let mid2 = right - third;
if arr[mid1] == target {
return Some(mid1);
}
if arr[mid2] == target {
return Some(mid2);
}
if target < arr[mid1] {
right = mid1 - 1;
} else if target > arr[mid2] {
left = mid2 + 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
None
}
fn main() {
let numbers = [5, 15, 25, 35, 45];
let target = 50;
println!("Array: {:?}", numbers);
match ternary_search_early_exit(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Early exit prevents unnecessary calculations when the target is obviously out of range, which can be helpful for large arrays.
Frequently Asked Questions (FAQ)
Q1: What is the time complexity of Ternary Search?
It is O(log₃ n), which is slightly faster than Binary Search in terms of divisions but comparable in practice.
Q2: Can Ternary Search work on unsorted arrays?
No. The array must be sorted for Ternary Search to function correctly.
Q3: When is Ternary Search better than Binary Search?
It can be advantageous in certain optimization problems, but for general sorted arrays, Binary Search is usually preferred.
Q4: Can Ternary Search handle floating-point numbers?
Yes, but you must use a small threshold for comparison to handle precision issues.
Q5: Is Ternary Search recursive or iterative?
It can be implemented both ways. Recursion is cleaner and more intuitive for beginners, while iteration is more memory-efficient.
Conclusion
Ternary Search is an efficient, divide-and-conquer algorithm suitable for sorted arrays. Rust implementations demonstrate both iterative and recursive approaches, as well as handling floating-point numbers and early exit optimization. Practicing Ternary Search helps beginners understand array traversal, conditional logic, and the concept of splitting a problem into smaller parts. By experimenting with these examples, you can strengthen your skills in both Rust programming and algorithmic thinking.
