The ternary search algorithm is a divide-and-conquer search algorithm that is used to find a specific element in a sorted array. Unlike binary search, which divides the array into two parts, ternary search divides the array into three parts.

Algorithm Explanation

In a ternary search, the following steps are followed:

1. Calculate the two midpoints:
   • mid1 = left + (right - left) / 3
   • mid2 = right - (right - left) / 3
2. Compare the target value with the values at mid1 and mid2.
3. If the target is equal to the value at mid1, return mid1.
4. If the target is equal to the value at mid2, return mid2.
5. If the target is less than the value at mid1, search in the left third.
6. If the target is greater than the value at mid2, search in the right third.
7. Otherwise, search in the middle third.

Go Program Implementation

package main

import (
    "fmt"
)

// TernarySearch performs a ternary search on a sorted array.
func TernarySearch(arr []int, left int, right int, target int) int {
    if right >= left {
        // Calculate midpoints
        mid1 := left + (right-left)/3
        mid2 := right - (right-left)/3

        // Check if target is at mid1
        if arr[mid1] == target {
            return mid1
        }

        // Check if target is at mid2
        if arr[mid2] == target {
            return mid2
        }

        // Determine which segment to search
        if target < arr[mid1] { return TernarySearch(arr, left, mid1-1, target) // Search in the left third } else if target > arr[mid2] {
            return TernarySearch(arr, mid2+1, right, target) // Search in the right third
        } else {
            return TernarySearch(arr, mid1+1, mid2-1, target) // Search in the middle third
        }
    }

    return -1 // Target not found
}

func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    target := 5

    result := TernarySearch(arr, 0, len(arr)-1, target)

    if result != -1 {
        fmt.Printf("Element %d found at index %d.\n", target, result)
    } else {
        fmt.Println("Element not found.")
    }
}

Program Structure

• Package Declaration: The program starts with the declaration of the main package.
• Imports: The fmt package is imported for output formatting.
• TernarySearch Function: This function takes an array, left and right indices, and the target value. It implements the ternary search algorithm.
• Main Function: This is the entry point of the program where the sorted array and target value are defined. The TernarySearch function is called, and the result is printed.

Conclusion

The ternary search algorithm is efficient for sorted arrays, providing an alternative to binary search. Although it is less commonly used due to its increased complexity, it can be advantageous in specific scenarios.