Working of Ternary Search

Ternary search is based on the divide-and-conquer strategy. It works as follows:

1. Divide the dataset into three parts.
2. Compare the target element with the elements at the two division points.
3. Depending on the comparisons, you can eliminate one-third of the dataset.
4. Repeat the process until you find the target element or exhaust the search space.

Let’s illustrate this with a simple example.

Consider a sorted array ‘arr’:

arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}

Suppose we want to find the index of the element 13 using ternary search. The algorithm proceeds as follows:

1. In each step, we divide the array into three parts and compare the middle elements.
2. Based on the comparison, we eliminated one-third of the dataset.
3. This process continues until we find the target element or determine it doesn’t exist in the dataset.

When searching for a specific element in a sorted dataset, many programmers are familiar with binary search. Binary search efficiently narrows down the search space by dividing it into two halves repeatedly. But there’s another search algorithm that can be even more efficient in certain scenarios.

Ternary search is a searching algorithm that efficiently locates an element in a sorted dataset by dividing it into three parts, rather than two, as in binary search. This additional partitioning can lead to a faster search in some cases. While binary search reduces the search space by half in each iteration, ternary search narrows it down to two-thirds.

Prerequisites: C Loops, Arrays, Binary Search and Recursion