Ternary Search Algorithm: Divide Array into Three Parts

The Ternary Search Algorithm is a powerful divide and conquer technique used to find an element in a sorted array. Unlike the more common binary search, which divides the array into two parts, ternary search divides it into three equal segments. This approach reduces the search space faster in certain cases, especially for unimodal functions or strictly sorted data, making it an important tool in algorithm design and analysis.

What is Ternary Search?

Ternary search is a divide and conquer algorithm that works only on sorted arrays or monotonic functions. The array is divided into three parts using two mid-points. By comparing the target element with the values at these mid-points, the algorithm discards one-third of the search space and continues the search in the remaining segment.

How Ternary Search Works?

Here’s a step-by-step explanation:

1. Start with the left index and right index of the sorted array.
2. Find two midpoints:

   mid1 = left + (right - left) / 3
   mid2 = right - (right - left) / 3

3. Compare the target element with arr[mid1] and arr[mid2].
4. If the target equals either, return its index.
5. If the target is smaller than arr[mid1], search in the left segment.
6. If the target is greater than arr[mid2], search in the right segment.
7. Otherwise, search in the middle segment.

Python Implementation of Ternary Search

Here’s a simple implementation in Python with recursion:

def ternary_search(arr, left, right, target):
    if left > right:
        return -1
    
    mid1 = left + (right - left) // 3
    mid2 = right - (right - left) // 3
    
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    
    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)

# Example usage
arr = [2, 4, 6, 8, 10, 12, 14, 16]
target = 10
result = ternary_search(arr, 0, len(arr) - 1, target)

print("Element found at index:", result)

Output:

Element found at index: 4

Illustrative Example

Suppose we are searching for 15 in the sorted array:

[5, 10, 15, 20, 25, 30, 35, 40]

• Initial midpoints are calculated at indices 2 and 5.
• arr[2] = 15, which matches the target.
• The algorithm successfully finds it in the first step!

Complexity Analysis

• Time Complexity: O(log3 n) → Slightly slower than binary search’s O(log2 n) in practical situations, but valuable in optimization problems.
• Space Complexity: O(1) in iterative implementation, O(log n) in recursive due to the call stack.

Ternary Search vs Binary Search

When to Use Ternary Search?

Ternary search is particularly useful when:

• The problem involves optimization of a unimodal function.
• The dataset is sorted and comparisons are relatively cheap.
• When designing algorithms that benefit from splitting into more than two sections (such as competitive programming problems).

Conclusion

The Ternary Search Algorithm is a great example of the divide and conquer paradigm applied in an alternative way to binary search. While binary search is more common for searching sorted arrays, ternary search becomes very useful in specific scenarios like function optimization and competitive programming challenges. Understanding both helps you become a stronger problem solver and programmer.