Ternary Search is an efficient algorithm for finding an element in a sorted array. Unlike Binary Search, which splits the array into two halves, Ternary Search divides it into three parts and determines which segment may contain the target. By reducing the search space more aggressively, Ternary Search can be slightly faster in some cases and offers an interesting way for beginners to understand divide-and-conquer strategies.
This algorithm is especially useful in scenarios where datasets are large, and comparisons are expensive, such as searching in sorted numeric datasets, financial records, or scientific measurements. For beginners learning R programming, implementing Ternary Search is a great exercise in understanding recursion, loops, and array indexing. It also demonstrates how thinking about the search process differently can improve efficiency while reinforcing foundational programming concepts.
Program 1: Basic Ternary Search using recursion
This program demonstrates the classic recursive approach to Ternary Search, dividing the array into three segments at each step.
ternary_search <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target < arr[mid1]) return(ternary_search(arr, target, left, mid1 - 1))
else if (target > arr[mid2]) return(ternary_search(arr, target, mid2 + 1, right))
else return(ternary_search(arr, target, mid1 + 1, mid2 - 1))
}
data <- c(5, 10, 15, 20, 25)
target <- 15
print(ternary_search(data, target))This program works by recursively narrowing the search space. Beginners can see how dividing into three parts reduces the search range faster than checking elements one by one.
Program 2: Iterative Ternary Search
This example shows how Ternary Search can also be implemented using a while loop, which may be preferred when recursion is not ideal.
ternary_search_iter <- function(arr, target) {
left <- 1
right <- length(arr)
while (left <= right) {
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target < arr[mid1]) right <- mid1 - 1
else if (target > arr[mid2]) left <- mid2 + 1
else {
left <- mid1 + 1
right <- mid2 - 1
}
}
return(-1)
}
data <- c(1, 3, 5, 7, 9, 11)
target <- 7
print(ternary_search_iter(data, target))Using iteration avoids recursive function calls, which is helpful for beginners who want a straightforward, loop-based approach.
Program 3: Ternary Search with negative numbers
Ternary Search works on arrays containing negative numbers, as long as the array is sorted in ascending order.
ternary_search <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target < arr[mid1]) return(ternary_search(arr, target, left, mid1 - 1))
else if (target > arr[mid2]) return(ternary_search(arr, target, mid2 + 1, right))
else return(ternary_search(arr, target, mid1 + 1, mid2 - 1))
}
data <- c(-30, -20, -10, 0, 10)
target <- -10
print(ternary_search(data, target))This teaches beginners that the algorithm is not limited to positive integers and is useful for datasets with negative values, such as financial losses or temperature readings.
Program 4: Ternary Search with floating-point numbers
You can also use Ternary Search on decimal numbers, which is useful for scientific or financial data.
ternary_search <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target < arr[mid1]) return(ternary_search(arr, target, left, mid1 - 1))
else if (target > arr[mid2]) return(ternary_search(arr, target, mid2 + 1, right))
else return(ternary_search(arr, target, mid1 + 1, mid2 - 1))
}
data <- c(1.1, 2.3, 3.5, 4.7, 5.9)
target <- 4.7
print(ternary_search(data, target))Beginners learn that the search logic is the same for floating-point numbers, provided the array remains sorted.
Program 5: Ternary Search for multiple occurrences
This example modifies the recursive approach to return the first occurrence of a duplicate element in the array.
ternary_search_first <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) {
while (mid1 > 1 && arr[mid1 - 1] == target) mid1 <- mid1 - 1
return(mid1)
}
if (arr[mid2] == target) {
while (mid2 > 1 && arr[mid2 - 1] == target) mid2 <- mid2 - 1
return(mid2)
}
if (target < arr[mid1]) return(ternary_search_first(arr, target, left, mid1 - 1))
else if (target > arr[mid2]) return(ternary_search_first(arr, target, mid2 + 1, right))
else return(ternary_search_first(arr, target, mid1 + 1, mid2 - 1))
}
data <- c(2, 4, 4, 4, 6, 8)
target <- 4
print(ternary_search_first(data, target))This program shows beginners how small modifications can adapt Ternary Search to handle real-world problems, like duplicates in datasets.
Program 6: Ternary Search with input validation
Adding checks for sorted arrays ensures the algorithm only runs on valid input, which is a best practice for beginners.
ternary_search <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target < arr[mid1]) return(ternary_search(arr, target, left, mid1 - 1))
else if (target > arr[mid2]) return(ternary_search(arr, target, mid2 + 1, right))
else return(ternary_search(arr, target, mid1 + 1, mid2 - 1))
}
ternary_search_safe <- function(arr, target) {
if (!all(diff(arr) >= 0)) stop("Array must be sorted in ascending order")
ternary_search(arr, target)
}
data <- c(3, 6, 9, 12)
target <- 9
print(ternary_search_safe(data, target))This version teaches beginners the importance of input validation to prevent errors.
Program 7: Ternary Search with descending arrays
With slight adjustments, Ternary Search can work on arrays sorted in descending order.
ternary_search_desc <- function(arr, target, left = 1, right = length(arr)) {
if (left > right) return(-1)
third <- floor((right - left) / 3)
mid1 <- left + third
mid2 <- right - third
if (arr[mid1] == target) return(mid1)
if (arr[mid2] == target) return(mid2)
if (target > arr[mid1]) return(ternary_search_desc(arr, target, left, mid1 - 1))
else if (target < arr[mid2]) return(ternary_search_desc(arr, target, mid2 + 1, right))
else return(ternary_search_desc(arr, target, mid1 + 1, mid2 - 1))
}
data <- c(50, 40, 30, 20, 10)
target <- 30
print(ternary_search_desc(data, target))This example shows beginners that algorithms are flexible and can be adapted to different data orders with small logical changes.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Ternary Search in R.
Q1. Can Ternary Search work on unsorted arrays?
No, it requires a sorted array to split it logically into three segments.
Q2. How is Ternary Search different from Binary Search?
Ternary Search splits the array into three parts instead of two, potentially reducing comparisons in some scenarios.
Q3. Can Ternary Search handle negative and decimal numbers?
Yes, as long as the array is sorted, Ternary Search works with any numeric values.
Q4. Can Ternary Search find the first occurrence among duplicates?
Yes, with minor modifications, it can locate the first occurrence or all duplicates.
Conclusion
Ternary Search is a powerful algorithm for efficiently searching sorted arrays, using a divide-and-conquer approach to narrow down the search space quickly. By splitting the array into three segments, it can offer performance improvements and introduces beginners to advanced problem-solving strategies.
Through these examples, beginners can practice recursive and iterative implementations, handle negative and decimal numbers, adapt the algorithm for descending arrays, and manage duplicates. Exploring Ternary Search strengthens understanding of array handling, recursion, and efficient searching techniques, preparing learners for more complex algorithms in R.
