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
{
static int ternSearch(int ar[], int start, int end, int num) { while (end >= start) {
// Finding mid1 and mid2 int mid1 = start + (end - start) / 3; int mid2 = end - (end - start) / 3;
// Comparing num with mid1 and mid2 if (ar[mid1] == num) { return mid1; }
if (ar[mid2] == num) { return mid2; }
// If not at mid1 or mid2 if (num < ar[mid1]) {
// If the num is between start and mid1 end = mid1 - 1; }
else if (num > ar[mid2]) {
// If the num is between mid2 and end start = mid2 + 1; }
else {
// If the num is between mid1 and mid2 start = mid1 + 1; end = mid2 - 1; } }
// If the num is not found return -1; }
public static void main(String args[]) { int start, end, p, num;
// Sort the array if not sorted int ar[] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
// Starting index start = 0;
// Length of the given array end = ar.length - 1;
// Checking for the number 8
// Number to be searched in the array num = 8;
/*
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.
*/ p = ternSearch(ar, start , end, num);
// Printing the result output System.out.println("Index of " + num + " in the array is " + p);
// Checking for 50, which is not present in the array
// num to be searched in the array num = 50;
// Search the num using ternSearch p = ternSearch(ar, start, end, num);
// Print the result for 50 System.out.println("Index of " + num + " is " + 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).
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 Coding Ninjas Studio 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
Live masterclass
Using Netflix data to master Power BI : Ace Data Analytics interview
by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO
07 Nov, 2024
01:30 PM
Get hired as an Amazon SDE : Resume building tips
by Anubhav Sinha, SDE2 @ Amazon
05 Nov, 2024
01:30 PM
Using Netflix data to master Power BI : Ace Data Analytics interview
by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO