Searching is a fundamental operation in programming, and while Linear Search and Binary Search are widely known, Ternary Search provides another efficient approach for sorted arrays. Ternary Search works by dividing the array into three equal parts instead of two, like in Binary Search. It compares the target element with two mid-points, narrowing down the search range more quickly in certain cases.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is especially useful for sorted datasets and in scenarios where you want to reduce the number of comparisons compared to Linear Search. It demonstrates the concept of divide-and-conquer, which is widely used in algorithms. For beginners, learning Ternary Search helps strengthen understanding of array indexing, recursion, and algorithmic thinking in GoLang.
Program 1: Iterative Ternary Search
This program demonstrates the classic iterative Ternary Search approach, where the array is split into three parts, and the search continues in the relevant segment.
package main
import "fmt"
func ternarySearchIterative(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
third := (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
}
func main() {
numbers := []int{5, 10, 15, 20, 25, 30, 35, 40}
target := 25
index := ternarySearchIterative(numbers, target)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}In this example, the array is divided into three segments using two midpoints. The search then continues in the relevant segment, reducing comparisons. Beginners can see how splitting the array more than twice can still efficiently locate elements in sorted arrays.
Program 2: Recursive Ternary Search
Recursion is a natural fit for Ternary Search, where the function calls itself on the segment likely containing the target element.
package main
import "fmt"
func ternarySearchRecursive(arr []int, target, left, right int) int {
if left > right {
return -1
}
third := (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 ternarySearchRecursive(arr, target, left, mid1-1)
} else if target > arr[mid2] {
return ternarySearchRecursive(arr, target, mid2+1, right)
} else {
return ternarySearchRecursive(arr, target, mid1+1, mid2-1)
}
}
func main() {
numbers := []int{3, 6, 9, 12, 15, 18, 21, 24, 27}
target := 18
index := ternarySearchRecursive(numbers, target, 0, len(numbers)-1)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This recursive approach makes it easy for beginners to understand how the search space shrinks at each step. It’s a great introduction to divide-and-conquer thinking and recursive problem-solving in GoLang.
Program 3: Ternary Search with Step Printing
Sometimes it’s helpful to see how Ternary Search works step by step. This version prints the midpoints and the segment being searched.
package main
import "fmt"
func ternarySearchPrint(arr []int, target, left, right int) int {
if left > right {
return -1
}
third := (right - left) / 3
mid1 := left + third
mid2 := right - third
fmt.Printf("Searching between indices %d and %d, mid1=%d, mid2=%d\n", left, right, mid1, mid2)
if arr[mid1] == target {
return mid1
}
if arr[mid2] == target {
return mid2
}
if target < arr[mid1] {
return ternarySearchPrint(arr, target, left, mid1-1)
} else if target > arr[mid2] {
return ternarySearchPrint(arr, target, mid2+1, right)
} else {
return ternarySearchPrint(arr, target, mid1+1, mid2-1)
}
}
func main() {
numbers := []int{2, 4, 6, 8, 10, 12, 14, 16, 18}
target := 12
index := ternarySearchPrint(numbers, target, 0, len(numbers)-1)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}By printing each step, beginners can visualize how the search space shrinks and why the algorithm is efficient. It’s a simple way to combine learning recursion with understanding Ternary Search logic.
Program 4: Ternary Search for Multiple Occurrences
Sometimes a target element may appear multiple times. This program extends Ternary Search to locate all occurrences.
package main
import "fmt"
func ternarySearchAll(arr []int, target int) []int {
indices := []int{}
index := ternarySearchRecursive(arr, target, 0, len(arr)-1)
if index == -1 {
return indices
}
// Check left side
left := index - 1
for left >= 0 && arr[left] == target {
indices = append([]int{left}, indices...)
left--
}
// Add middle index
indices = append(indices, index)
// Check right side
right := index + 1
for right < len(arr) && arr[right] == target {
indices = append(indices, right)
right++
}
return indices
}
func ternarySearchRecursive(arr []int, target, left, right int) int {
if left > right {
return -1
}
third := (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 ternarySearchRecursive(arr, target, left, mid1-1)
} else if target > arr[mid2] {
return ternarySearchRecursive(arr, target, mid2+1, right)
} else {
return ternarySearchRecursive(arr, target, mid1+1, mid2-1)
}
}
func main() {
numbers := []int{5, 10, 10, 10, 15, 20, 25}
target := 10
indices := ternarySearchAll(numbers, target)
if len(indices) > 0 {
fmt.Printf("Element %d found at indices %v\n", target, indices)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This program finds one occurrence of the target and then expands left and right to locate duplicates. It’s useful in real datasets where repeated values are common and teaches beginners how to extend standard algorithms to practical scenarios.
Frequently Asked Questions (FAQ)
Ternary Search can feel unfamiliar at first. Here are some common questions:
Q1: What is Ternary Search?
Ternary Search is a divide-and-conquer algorithm that splits a sorted array into three parts to locate a target element.
Q2: How is it different from Binary Search?
Binary Search divides the array into two halves, while Ternary Search divides it into three parts, sometimes reducing the number of comparisons.
Q3: What is the time complexity of Ternary Search?
The time complexity is O(log₃ n), slightly faster than Binary Search in terms of the number of comparisons in some cases.
Q4: When should I use Ternary Search?
It’s best used for sorted arrays where you want to reduce comparisons compared to Linear Search and learn about divide-and-conquer strategies.
Q5: Can Ternary Search handle duplicate elements?
Yes, with minor adjustments, Ternary Search can find all occurrences of a target element efficiently.
Conclusion
Ternary Search is an elegant and efficient search algorithm that teaches key concepts like divide-and-conquer and recursive thinking. Starting with iterative implementation, beginners can explore recursion, step-by-step visualization, and handling duplicates to fully understand its practical applications.
Practicing Ternary Search in GoLang improves problem-solving skills and prepares programmers to tackle more advanced searching and optimization challenges. Once comfortable, these skills can be applied to real-world datasets and performance-critical applications.
