Java Program to Implement Ternary Search Algorithm

«
»
This is a Java Program to Implement Ternary Search Algorithm. A ternary search algorithm is a technique in computer science for finding the minimum or maximum of an increasing or decreasing function. A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two-thirds. A ternary search is an example of a divide and conquer algorithm.

Here is the source code of the Java Program to Implement Ternary Search Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Ternary Search Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class TernarySearch **/
  8. public class TernarySearch
  9. {
  10.     /** call function **/
  11.     public static int ternarySearch (int[] A, int value)
  12.     {
  13.         return ternarySearch(A, value, 0, A.length - 1);
  14.     }
  15.     /** TernarySearch function **/
  16.     public static int ternarySearch (int[] A, int value, int start, int end)
  17.     {
  18.         if (start > end) 
  19.             return -1;       
  20.  
  21.         /** First boundary: add 1/3 of length to start **/
  22.         int mid1 = start + (end-start) / 3;        
  23.         /** Second boundary: add 2/3 of length to start **/
  24.         int mid2 = start + 2*(end-start) / 3;
  25.  
  26.         if (A[mid1] == value) 
  27.             return mid1;
  28.  
  29.         else if (A[mid2] == value) 
  30.             return mid2;
  31.         /** Search 1st third **/
  32.         else if (value < A[mid1]) 
  33.             return ternarySearch (A, value, start, mid1-1);
  34.         /** Search 3rd third **/
  35.         else if (value > A[mid2]) 
  36.             return ternarySearch (A, value, mid2+1, end);
  37.         /** Search middle third **/
  38.         else 
  39.             return ternarySearch (A, value, mid1,mid2);        
  40.     }
  41.     /** Main method **/
  42.     public static void main(String[] args) 
  43.     {
  44.         Scanner scan = new Scanner( System.in );        
  45.         System.out.println("Ternary Search Test\n");
  46.         int n, i;
  47.         /** Accept number of elements **/
  48.         System.out.println("Enter number of integer elements");
  49.         n = scan.nextInt();
  50.         /** Create integer array on n elements **/
  51.         int arr[] = new int[ n ];
  52.         /** Accept elements **/
  53.         System.out.println("\nEnter "+ n +" sorted integer elements");
  54.         for (i = 0; i < n; i++)
  55.             arr[i] = scan.nextInt();
  56.         System.out.println("\nEnter element to search for : ");
  57.         int key = scan.nextInt();
  58.  
  59.         int result = ternarySearch(arr, key);
  60.  
  61.         if (result == -1)
  62.             System.out.println("\n"+ key +" element not found");
  63.         else
  64.             System.out.println("\n"+ key +" element found at position "+ result);
  65.  
  66.     }    
  67. }

advertisement
Ternary Search Test
 
Enter number of integer elements
10
 
Enter 10 sorted integer elements
2 5 15 24 31 47 59 61 79 97
 
Enter element to search for :
24
 
24 element found at position 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter