Introduction

Ternary search is a divide-and-conquer algorithm that is used to find the position of a target value within a sorted array.
Unlike binary search, which divides the array into two parts, ternary search divides the array into three parts.
It is particularly useful when the size of the array is large and the cost of comparisons is high.

Program Structure

The ternary search algorithm works by dividing the array into three segments. The steps are as follows:

1. Calculate two midpoints: mid1 and mid2.
2. Compare the target value with the elements at mid1 and mid2.
3. If the target is equal to one of the midpoints, return the index.
4. If the target is less than mid1, search in the left segment.
5. If the target is greater than mid2, search in the right segment.
6. If the target lies between mid1 and mid2, search in the middle segment.
7. Repeat the process until the target is found or the segment size is zero.

Python Implementation

def ternary_search(arr, left, right, target):
    if right >= left:
        # Calculate the midpoints
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3

        # Check if the target is at one of the midpoints
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2

        # Determine the segment to search
        if target < arr[mid1]: return ternary_search(arr, left, mid1 - 1, target) elif target > arr[mid2]:
            return ternary_search(arr, mid2 + 1, right, target)
        else:
            return ternary_search(arr, mid1 + 1, mid2 - 1, target)

    # Target not found
    return -1

# Example usage
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    target = 7
    result = ternary_search(arr, 0, len(arr) - 1, target)

    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")
    

Explanation of the Code

The program defines a function ternary_search that takes four parameters:

• arr: The sorted array in which to search.
• left: The starting index of the segment to search.
• right: The ending index of the segment to search.
• target: The value to find.

The function first checks if the current segment is valid (i.e., if right is greater than or equal to left).
It then calculates the two midpoints and compares the target with these midpoints.
Depending on the comparison results, it recursively searches the appropriate segment of the array.

Conclusion

Ternary search is an efficient searching algorithm for sorted arrays, especially in scenarios where multiple comparisons are costly.
Although it has a slightly higher overhead than binary search, it can be advantageous in specific use cases.