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

{

   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).

 

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think