Searching is a fundamental task in programming, and understanding different search algorithms is key to writing efficient programs. Ternary Search is an advanced search algorithm that is an extension of Binary Search. Instead of dividing the array into two halves, Ternary Search splits it into three parts. This makes it useful for sorted arrays, particularly when you want to minimize comparisons for large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is commonly applied in problems where the dataset is sorted, and you need to locate an element quickly, such as searching for an ID in a list, a particular score in a leaderboard, or any scenario with ordered numerical data. For beginners learning Kotlin, implementing Ternary Search provides an opportunity to understand divide-and-conquer strategies, recursion, and algorithm optimization in a simple and visual way.
Program 1: Iterative Ternary Search on Array
This program demonstrates the iterative approach to Ternary Search, where the array is split into three segments and the target is searched step by step.
fun ternarySearch(arr: IntArray, target: Int): Int {
var low = 0
var high = arr.size - 1
while (low <= high) {
val mid1 = low + (high - low) / 3
val mid2 = high - (high - low) / 3
when {
arr[mid1] == target -> return mid1
arr[mid2] == target -> return mid2
target < arr[mid1] -> high = mid1 - 1
target > arr[mid2] -> low = mid2 + 1
else -> {
low = mid1 + 1
high = mid2 - 1
}
}
}
return -1
}
fun main() {
val numbers = intArrayOf(10, 20, 30, 40, 50, 60, 70)
val target = 40
println("Array: ${numbers.joinToString()}")
val index = ternarySearch(numbers, target)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}The algorithm works by dividing the array into three parts and narrowing the search region according to the target’s position. Beginners can easily understand how segmenting reduces the number of comparisons compared to linear search.
Program 2: Recursive Ternary Search
Recursion is a natural fit for Ternary Search because the search space is reduced in each call. This program demonstrates a recursive implementation.
fun ternarySearchRecursive(arr: IntArray, target: Int, low: Int = 0, high: Int = arr.size - 1): Int {
if (low > high) return -1
val mid1 = low + (high - low) / 3
val mid2 = high - (high - low) / 3
return when {
arr[mid1] == target -> mid1
arr[mid2] == target -> mid2
target < arr[mid1] -> ternarySearchRecursive(arr, target, low, mid1 - 1)
target > arr[mid2] -> ternarySearchRecursive(arr, target, mid2 + 1, high)
else -> ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1)
}
}
fun main() {
val numbers = intArrayOf(5, 15, 25, 35, 45, 55)
val target = 25
println("Array: ${numbers.joinToString()}")
val index = ternarySearchRecursive(numbers, target)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}The recursive approach divides the array into three parts in every call. This demonstrates the divide-and-conquer principle, which is useful for beginners to understand algorithmic efficiency.
Program 3: Ternary Search on Kotlin List
Ternary Search is versatile and can also be applied to Kotlin List<Int> collections. This program shows how to implement it for a list.
fun ternarySearchList(list: List<Int>, target: Int): Int {
var low = 0
var high = list.size - 1
while (low <= high) {
val mid1 = low + (high - low) / 3
val mid2 = high - (high - low) / 3
when {
list[mid1] == target -> return mid1
list[mid2] == target -> return mid2
target < list[mid1] -> high = mid1 - 1
target > list[mid2] -> low = mid2 + 1
else -> {
low = mid1 + 1
high = mid2 - 1
}
}
}
return -1
}
fun main() {
val numbers = listOf(2, 4, 6, 8, 10, 12)
val target = 8
println("List: $numbers")
val index = ternarySearchList(numbers, target)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}This demonstrates that Ternary Search can be applied to different types of collections in Kotlin without much modification, making it a practical tool for real-world scenarios.
Program 4: Ternary Search with Duplicate Elements
When a dataset contains duplicates, you might want to locate the first occurrence of the target. This program adapts Ternary Search to do that.
fun ternarySearchFirst(arr: IntArray, target: Int): Int {
var low = 0
var high = arr.size - 1
var result = -1
while (low <= high) {
val mid1 = low + (high - low) / 3
val mid2 = high - (high - low) / 3
when {
arr[mid1] == target -> {
result = mid1
high = mid1 - 1
}
arr[mid2] == target -> {
result = mid2
high = mid2 - 1
}
target < arr[mid1] -> high = mid1 - 1
target > arr[mid2] -> low = mid2 + 1
else -> {
low = mid1 + 1
high = mid2 - 1
}
}
}
return result
}
fun main() {
val numbers = intArrayOf(10, 20, 20, 30, 40)
val target = 20
println("Array: ${numbers.joinToString()}")
val index = ternarySearchFirst(numbers, target)
if (index != -1) println("First occurrence of $target is at index $index")
else println("$target not found")
}This variation demonstrates how Ternary Search can be tailored to specific requirements, such as finding duplicates, which is common in real-world data processing.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Ternary Search in Kotlin.
Q1: What is Ternary Search?
Ternary Search is a search algorithm that divides a sorted dataset into three parts to locate a target element efficiently.
Q2: When should I use Ternary Search?
It is best used for large, sorted datasets where reducing comparisons faster than Binary Search is beneficial.
Q3: Can Ternary Search work with lists as well as arrays?
Yes, it works on Kotlin arrays and lists, making it versatile for different types of collections.
Q4: What is the time complexity?
The average and worst-case time complexity is O(log₃ n), which is slightly better than Binary Search in some theoretical scenarios.
Q5: Can Ternary Search be implemented recursively?
Yes, recursion is a natural fit because the array is divided into three parts in each call.
Conclusion
Ternary Search is an efficient and versatile algorithm for searching sorted datasets. In Kotlin, it can be implemented iteratively, recursively, or applied to arrays and lists. For beginners, practicing Ternary Search helps build a strong understanding of divide-and-conquer algorithms, recursion, and optimization strategies. By experimenting with variations, such as handling duplicates or adapting for different collections, learners can strengthen their problem-solving skills and create more efficient programs.
