Ternary Search is an efficient searching algorithm designed to work with sorted arrays. Unlike Binary Search, which splits the search space into two parts, Ternary Search divides it into three equal sections. This approach allows the algorithm to check two midpoints in each iteration, which can reduce the number of comparisons in some cases.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is particularly useful when working with large, sorted datasets where each comparison or access is costly. It can be applied in tasks such as finding values in databases, searching numeric sequences, or optimizing performance-critical applications. Learning Ternary Search in Scala helps beginners understand recursive thinking, search space division, and efficient comparison strategies. It also introduces the idea of splitting a problem into more than two parts for optimization.
Program 1: Iterative Ternary Search
This program demonstrates the basic iterative approach to Ternary Search in a sorted integer array.
object TernarySearchIterative {
def ternarySearch(arr: Array[Int], target: Int): Int = {
var left = 0
var right = arr.length - 1
while (left <= right) {
val mid1 = left + (right - left) / 3
val mid2 = right - (right - left) / 3
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
}
}
-1
}
def main(args: Array[String]): Unit = {
val data = Array(1, 3, 5, 7, 9, 11, 13)
val target = 7
val index = ternarySearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This iterative approach divides the array into three parts and checks the two midpoints. Beginners can see how the search space reduces efficiently in each iteration, which helps understand the power of multi-way search.
Program 2: Recursive Ternary Search
Recursive implementation of Ternary Search shows how dividing the search space into three parts can be handled elegantly with recursion.
object TernarySearchRecursive {
def ternarySearch(arr: Array[Int], target: Int, left: Int = 0, right: Int = -1): Int = {
val r = if (right == -1) arr.length - 1 else right
if (left > r) return -1
val mid1 = left + (r - left) / 3
val mid2 = r - (r - left) / 3
if (arr(mid1) == target) mid1
else if (arr(mid2) == target) mid2
else if (target < arr(mid1)) ternarySearch(arr, target, left, mid1 - 1)
else if (target > arr(mid2)) ternarySearch(arr, target, mid2 + 1, r)
else ternarySearch(arr, target, mid1 + 1, mid2 - 1)
}
def main(args: Array[String]): Unit = {
val data = Array(2, 4, 6, 8, 10, 12, 14)
val target = 10
val index = ternarySearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}The recursive approach simplifies the logic of narrowing down the search space. Beginners can learn how recursive calls manage different segments of the array efficiently.
Program 3: Ternary Search for Floating-Point Numbers
Ternary Search can also handle arrays of floating-point numbers as long as they are sorted.
object TernarySearchFloat {
def ternarySearch(arr: Array[Double], target: Double): Int = {
var left = 0
var right = arr.length - 1
while (left <= right) {
val mid1 = left + (right - left) / 3
val mid2 = right - (right - left) / 3
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
}
}
-1
}
def main(args: Array[String]): Unit = {
val data = Array(1.1, 2.2, 3.3, 4.4, 5.5)
val target = 3.3
val index = ternarySearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This program teaches beginners that Ternary Search is flexible and works with numeric data types beyond integers.
Program 4: Ternary Search with Multiple Occurrences
This program finds all positions of a target when the array contains duplicate values.
object TernarySearchMultiple {
def ternarySearchAll(arr: Array[Int], target: Int): Array[Int] = {
val n = arr.length
var left = 0
var right = n - 1
val indices = scala.collection.mutable.ArrayBuffer[Int]()
while (left <= right) {
val mid1 = left + (right - left) / 3
val mid2 = right - (right - left) / 3
if (arr(mid1) == target) indices += mid1
if (arr(mid2) == target) indices += mid2
if (target < arr(mid1)) right = mid1 - 1
else if (target > arr(mid2)) left = mid2 + 1
else {
left = mid1 + 1
right = mid2 - 1
}
}
indices.sorted.toArray
}
def main(args: Array[String]): Unit = {
val data = Array(2, 4, 4, 4, 6, 8)
val target = 4
val indices = ternarySearchAll(data, target)
if (indices.nonEmpty) println(s"Element $target found at indices: ${indices.mkString(", ")}")
else println(s"Element $target not found")
}
}This shows how Ternary Search can be adapted to find all occurrences. Beginners learn how to collect multiple results while keeping the search efficient.
Program 5: Recursive Ternary Search for Floating-Point Numbers
A recursive variant for floating-point arrays demonstrates flexibility and elegance in code.
object TernarySearchFloatRecursive {
def ternarySearch(arr: Array[Double], target: Double, left: Int = 0, right: Int = -1): Int = {
val r = if (right == -1) arr.length - 1 else right
if (left > r) return -1
val mid1 = left + (r - left) / 3
val mid2 = r - (r - left) / 3
if (arr(mid1) == target) mid1
else if (arr(mid2) == target) mid2
else if (target < arr(mid1)) ternarySearch(arr, target, left, mid1 - 1)
else if (target > arr(mid2)) ternarySearch(arr, target, mid2 + 1, r)
else ternarySearch(arr, target, mid1 + 1, mid2 - 1)
}
def main(args: Array[String]): Unit = {
val data = Array(1.5, 2.5, 3.5, 4.5, 5.5)
val target = 4.5
val index = ternarySearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}Recursive floating-point search shows that Ternary Search principles work across numeric types and recursion makes the logic clear for beginners.
Frequently Asked Questions (FAQ)
This section answers common questions beginners often have about Ternary Search in Scala.
Q1: What is Ternary Search?
Ternary Search is a search algorithm that divides a sorted array into three parts and checks two midpoints to locate the target.
Q2: How is Ternary Search different from Binary Search?
Binary Search splits the array into two parts; Ternary Search splits it into three, potentially reducing comparisons in some cases.
Q3: Can Ternary Search handle floating-point numbers?
Yes, as long as the array is sorted and numeric.
Q4: When should I use Ternary Search?
It is best for large, sorted datasets and when multiple comparisons per iteration are acceptable.
Q5: Can Ternary Search find multiple occurrences?
Yes, by collecting all indices during the search within the relevant segments.
Conclusion
Ternary Search is a powerful algorithm for efficiently searching sorted arrays. By understanding both iterative and recursive implementations in Scala, beginners can see how dividing the search space into three parts reduces comparisons and optimizes search time. Practicing with integers, floating-point numbers, and multiple occurrences helps learners build confidence in applying search algorithms and prepares them for more advanced algorithmic challenges.
