Ternary Search
Introduction
Among all searching techniques, the ternary sort has advantages of its own. After explaining what this technique is about and how it works, the article will further explain the algorithm and its time and space complexity for average, best and worst cases.
In this blog, we have also used an example and its code snippet to understand the concept better.
What is Ternary Search?
Ternary search is a searching technique used to find out the position of any given element in a sorted array. While the array is divided into two parts for binary search where just one mid element is used, ternary search requires the array to be divided into three parts and has two mid elements. However, the array to be searched using this technique must be sorted.
Algorithm
- The key is compared with the first mid element, ‘mid1’. If equal, ‘mid1’ is returned. If not equal, the key is next compared with ‘mid2’, and the same would be returned if equal.
- If not equal to either ‘mid1’ or ‘mid2’, the key is checked to be lesser than ‘mid1’. If it is, then we recur to the first part.
- If it is not, then the key is checked to be greater than ‘mid2’. If yes, then we will recur to the third part of the array.
- If not, then we recur to the middle part of the array.
Example with Code snippet:
public class tSearch Search the num using ternSearch by sending arguments. The function would return the index of "num" if present, or '-1' if not. This would be stored in p. */ |
Output
Index of 8 is 4 Index of 50 is -1 |
Time Complexity
Suppose the algorithm involves ‘N’ steps. The searchable range would be the size = 3N. Inversely, the number of steps needed to find the element is the log of the size of the collection. So the runtime is O(log N).
The time complexity for ternary search is O (log N ) on average.
Best case time complexity is O(1), and worst-case complexity is O (log N)
Space Complexity
The space complexity is O(1). As Constant space is used in the approach, therefore overall space complexity is O(1).
Frequently Asked Questions
What is the advantage of ternary search?
Ternary search is straightforward to implement and less prone to errors when dealing with floating-point integers. This technique can be used when the function cannot be differentiated.
Is ternary search a divide and conquer algorithm?
Ternary search divides the array into three parts to determine if the maximum or minimum element is in the first third, the last one or the middle one. Therefore it is an example of a divide-and-conquer algorithm.
Why is binary search better than ternary search?
Binary search makes fewer comparisons than ternary search in the worst case. Hence, it is the better option out of the two.
Which searching algorithm is the best of all?
The efficiency of ternary search, binary search and other search algorithms is calculated by the number of comparisons made to search for the given element in the worst case. Binary search is the best search algorithm considering this aspect.
Key takeaways
In this article, we learned how the ternary search algorithm works and how it is implemented, along with an example. We also discussed its advantages and disadvantages, besides the time and space complexity for the ternary sort.
You can go to CodeStudio and try solving problems. Share this blog with your friends if you found it helpful! Until then, All the best for your future endeavours, and Keep Coding.
By Reet Maggo
Comments
No comments yet
Be the first to share what you think