Friday, February 8, 2019

Ternary Search Program in Java

In this post we’ll see how to write Ternary search program in Java. Ternary search is a divide and conquer algorithm just like Binary search how it differs is that the array is divided into three parts rather than two which reduces the range of search by 1/3 in each iteration.

How does Ternary search work

One of the prerequisite for the Ternary search is that the input array should be sorted.

In each iteration searched element is compared with two middle elements (mid1 and mid2) calculated for the 1/3rd parts.

If searched element is less than mid1 that means the searched element should be in between the start element and mid1 as the array is sorted.

If searched element is greater than mid1 but less than mid2 that means the searched element should be in between the mid1 and mid2.

If searched element is greater than mid2 that means the searched element is in the last 1/3rd part of the array.

In the next iteration search is done with in that 1/3rd part of the array where the searched element lies.

This process of division and searching continues unless the element is found or the length of the sub-array becomes 0 which means searched element is not found in the array.

Following image shows the process of division in each iteration.

Ternary search in Java

Ternary search Java program

public class TernarySearch {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73};
        Arrays.sort(arr);
        System.out.println("sorted array- " + Arrays.toString(arr));
        System.out.println("Enter value to search: ");
        int searchElement = sc.nextInt();
        int index = ternarySearch(arr, 0, arr.length-1, searchElement);
        if(index != -1){
            System.out.println("Searched item " + arr[index] + " found at index "+index);
        }else{
            System.out.println("Searched item " + searchElement + " not found in the array");
        }
    }
    
    private static int ternarySearch(int[] arr, int start, int end, int searchElement){
        // exit condition
        if(start > end){
            return -1;
        }
        int mid1 = start + (end - start)/3;
        int mid2 = start + 2*(end - start)/3;
        System.out.println("start-" + start + " end- " + end + " mid1- " + mid1 + " mid2- " + mid2);
        if(searchElement == arr[mid1]){
            return mid1;
        }
        if(searchElement == arr[mid2]){
            return mid2;
        }
        // first 1/3
        if(searchElement < arr[mid1]){
            return ternarySearch(arr, start, mid1-1, searchElement);
        }else if (searchElement > arr[mid2]){
            // last 1/3
            return ternarySearch(arr, mid2+1, end, searchElement);
            
        }else{
            // mid 1/3
            return ternarySearch(arr, mid1+1, mid2-1, searchElement);
        }
    }
}

Output for few searches:

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
68
start-0 end- 8 mid1- 2 mid2- 5
start-6 end- 8 mid1- 6 mid2- 7
Searched item 68 found at index 7

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
10
start-0 end- 8 mid1- 2 mid2- 5
Searched item 10 found at index 2

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
90
start-0 end- 8 mid1- 2 mid2- 5
start-6 end- 8 mid1- 6 mid2- 7
start-8 end- 8 mid1- 8 mid2- 8
Searched item 90 not found in the array

Performance of Ternary search

Time complexity of Ternary search is O(log3n) but the comparisons are more in Ternary search.

Space complexity of Ternary search is O(1) as no auxiliary space is needed. Though recursive solution will have method stacks for each recursive call making the space complexity as O(logn).

That's all for this topic Ternary Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Linear Search (Sequential Search) Java Program
  2. Bucket Sort Program in Java
  3. Count Total Number of Times Each Character Appears in a String - Java Program
  4. Array Rotation Java Program
  5. Print Odd-Even Numbers Using Threads And wait-notify - Java Program

You may also like-

  1. Zipping Files And Folders in Java
  2. How to Read File From The Last Line in Java
  3. Arrange Non-Negative Integers to Form Largest Number - Java Program
  4. Generating Getters And Setters Using Reflection - Java Program
  5. Nested Class And Inner Class in Java
  6. ResultSet Interface in Java-JDBC
  7. String Vs StringBuffer Vs StringBuilder in Java
  8. Installing Hadoop on a Single Node Cluster in Pseudo-Distributed Mode