Working of Ternary Search
The concept involves dividing the array into three equal segments and determining in which segment the key element is located. It works similarly to a binary search, with the distinction of reducing time complexity by dividing the array into three parts instead of two.
Below are the step-by-step explanation of working of Ternary Search:
- Initialization:
- Set two pointers, left and right, initially pointing to the first and last elements of our search space.
- Divide the search space:
- Calculate two midpoints, mid1 and mid2, dividing the current search space into three roughly equal parts:
- mid1 = left + (right – left) / 3
- mid2 = right – (right – left) / 3
- The array is now effectively divided into [left, mid1], (mid1, mid2), and [mid2, right].
- Comparison with Target:.
- If the target is equal to the element at mid1 or mid2, the search is successful, and the index is returned
- If the target is less than the element at mid1, update the right pointer to mid1 – 1.
- If the target is greater than the element at mid2, update the left pointer to mid2 + 1.
- If the target is between the elements at mid1 and mid2, update the left pointer to mid1 + 1 and the right pointer to mid2 – 1.
- Repeat or Conclude:
- Repeat the process with the reduced search space until the target is found or the search space becomes empty.
- If the search space is empty and the target is not found, return a value indicating that the target is not present in the array.
Illustration:
Ternary Search
Computer systems use different methods to find specific data. There are various search algorithms, each better suited for certain situations. For instance, a binary search divides information into two parts, while a ternary search does the same but into three equal parts. It’s worth noting that ternary search is only effective for sorted data. In this article, we’re going to uncover the secrets of Ternary Search – how it works, why it’s faster in some situations.
Table of Content
- What is the Ternary Search?
- When to use Ternary Search
- Working of Ternary Search
- Implementation of Ternary Search
- Complexity Analysis of Ternary Search
- Binary search Vs Ternary Search
- Advantages
- Disadvantages
- Summary
Contact Us