Ternary Search Algorithm
The Ternary Search Algorithm is an advanced searching technique that is used to find the maximum or minimum value of a unimodal function or to search for a specific element in a sorted array. This divide-and-conquer algorithm works by dividing the search interval into three equal parts and then eliminating two of the three parts based on the values of the mid-points, ultimately narrowing down the search interval. Ternary search is most efficient when applied to functions that exhibit a unique maximum or minimum value and have a well-defined curvature.
In each iteration of the algorithm, two mid-points, say m1 and m2, are calculated by dividing the search interval into three equal parts. These mid-points are then compared with the target value or evaluated with the unimodal function. If the target value lies between the lower bound and m1, the search interval is updated to be between the lower bound and m1. If the target value lies between m1 and m2, the search interval is updated to be between m1 and m2. Lastly, if the target value lies between m2 and the upper bound, the search interval is updated to be between m2 and the upper bound. This process is repeated iteratively, narrowing down the search interval with each iteration, until the maximum or minimum value is found or the desired element is located. The time complexity of the ternary search algorithm is O(log3 N), which is slightly faster than the binary search algorithm with a time complexity of O(log2 N).
package TernarySearch
import (
"math/rand"
"testing"
"time"
)
func TernarySearch(array []int, number int) int {
minIndex := 0
maxIndex := len(array) - 1
for minIndex <= maxIndex {
midIndex1 := minIndex + int((maxIndex-minIndex)/3)
midIndex2 := maxIndex - int((maxIndex-minIndex)/3)
midItem1 := array[midIndex1]
midItem2 := array[midIndex2]
if midItem1 == number {
return midIndex1
} else if midItem2 == number {
return midIndex2
}
if midItem1 < number {
minIndex = midIndex1 + 1
} else if midItem2 > number {
maxIndex = midIndex2 - 1
} else {
minIndex = midIndex1 + 1
maxIndex = midIndex2 - 1
}
}
return -1
}
func SortArray(array []int) {
for itemIndex, itemValue := range array {
for itemIndex != 0 && array[itemIndex-1] > itemValue {
array[itemIndex] = array[itemIndex-1]
itemIndex -= 1
}
array[itemIndex] = itemValue
}
}
func TestTernarySearch(t *testing.T) {
random := rand.New(rand.NewSource(time.Now().UnixNano()))
array := make([]int, random.Intn(100-10)+10)
for i := range array {
array[i] = random.Intn(100)
}
SortArray(array)
for _, value := range array {
result := TernarySearch(array, value)
if result == -1 {
t.Fail()
}
}
}
