Java Program for Ternary Search

What is ternary search ?

Similarly like linear search and binary search, ternary search is a searching technique that is used to find the index or position of a particular value in collection of elements.

Ternary search is used only on a sorted collection of elements.

Ternary search, like binary search, is based on divide-and-conquer algorithm.

it is divided into 3 parts (where in binary search 2 parts) and then determines in which part the element exists.

Example, consider sorted collection of elements

collection sorted

Ternary Search Time complexity

Ternary search performs the search operation on the other 2/3 parts in every steps. this results in a worst case time complexity of O(log3N), where N is the number of elements in the collection.

Note:

Below Java programs return the index of an array and index starts with 0, so if 4th element matches in the array returns 3.

Java Program for Ternary Search using While loop

Reads array of integers as sorted order and finds the search key in an array of integers.

import java.util.*;

class TernarySearchTest {
	// Ternary search method which search key in the array of integers
	// using while loop
	static int ternarySearch(int[] numbers, int searchKey){   
		int leftIndex = 0;
		int rightIndex = numbers.length - 1;
	    while (rightIndex >= leftIndex){                                           
	        int midIndex1 = leftIndex + (rightIndex -leftIndex)/3;                  
	        int midIndex2 = rightIndex - (rightIndex - leftIndex)/3;                
	        if (numbers[midIndex1] == searchKey){                              
	            return midIndex1;                
	        }
	        if (numbers[midIndex2] == searchKey){                             
	            return midIndex2;                
	        }
	                                                                                
	        if (searchKey < numbers[midIndex1]){       
	        	rightIndex = midIndex1 - 1;
	        }
	        else if (searchKey > numbers[midIndex2]){                             
	            leftIndex = midIndex2 + 1;
	        }
	        else{                                                                  
	            leftIndex = midIndex1 + 1;
	            rightIndex = midIndex2 - 1;
	        }
	    }
	    return -1;
	 }

	// Gets the Array of Integers
	static int[] getNumbers(Scanner sc){
		int[] numbers;
		System.out.print("Enter Number of Elements: ");
		int count = sc.nextInt();
		numbers = new int[count];
		System.out.println();
		System.out.println("Enter Array Numbers:");
		for (int i=0;i<count;i++){
			numbers[i]=sc.nextInt();
		}
		return numbers;
	}
	public static void main(String[] args){
		int[] numbers;
		Scanner sc = new Scanner(System.in);
		numbers = getNumbers(sc);
		System.out.println();
		System.out.print("Enter Search Key: ");
		int searchKey = sc.nextInt();
		sc.close();
		int index = ternarySearch(numbers, searchKey);
		// Prints the result, index -1 indicates that key is not found,
		//otherwise index location where key is found in array of integers.
		if (index >= 0){
			System.out.println("Search key index in Array of Integers: "+index);
		} else {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}

Output:
D:\Java_Programs>javac TernarySearchTest.java
D:\Java_Programs>java TernarySearchTest 
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 3
Search key index in Array of Integers: 2

D:\Java_Programs>javac TernarySearchTest.java
D:\Java_Programs>java TernarySearchTest 
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 4
Search key index in Array of Integers: 3

D:\Java_Programs>javac TernarySearchTest.java
D:\Java_Programs>java TernarySearchTest 
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 6
Search key is not found in Array of Integers!

Java Program for Ternary Search using for loop

Reads array of integers as sorted order and finds the search key in an array of integers using for loop.

import java.util.*;

class TernarySearchTest {
	// Ternary search method which search key in the array of integers
	// using recursive method
	static int ternarySearch(int[] numbers, int searchKey){   

	    for (int leftIndex = 0, rightIndex = numbers.length - 1;(rightIndex >= leftIndex);){                                           
	        int midIndex1 = leftIndex + (rightIndex -leftIndex)/3;                  
	        int midIndex2 = rightIndex - (rightIndex - leftIndex)/3;                
	        if (numbers[midIndex1] == searchKey){                              
	            return midIndex1;                
	        }
	        if (numbers[midIndex2] == searchKey){                             
	            return midIndex2;                
	        }
	                                                                                
	        if (searchKey < numbers[midIndex1]){       
	        	rightIndex = midIndex1 - 1;
	        }
	        else if (searchKey > numbers[midIndex2]){                             
	            leftIndex = midIndex2 + 1;
	        }
	        else{                                                                  
	            leftIndex = midIndex1 + 1;
	            rightIndex = midIndex2 - 1;
	        }
	    }
	    return -1;
	 }

	// Gets the Array of Integers
	static int[] getNumbers(Scanner sc){
		int[] numbers;
		System.out.print("Enter Number of Elements: ");
		int count = sc.nextInt();
		numbers = new int[count];
		System.out.println();
		System.out.println("Enter Array Numbers:");
		for (int i=0;i<count;i++){
			numbers[i]=sc.nextInt();
		}
		return numbers;
	}
	public static void main(String[] args){
		int[] numbers;
		Scanner sc = new Scanner(System.in);
		numbers = getNumbers(sc);
		System.out.println();
		System.out.print("Enter Search Key: ");
		int searchKey = sc.nextInt();
		sc.close();
		int index = ternarySearch(numbers, searchKey);
		// Prints the result, index -1 indicates that key is not found,
		//otherwise index location where key is found in array of integers.
		if (index >= 0){
			System.out.println("Search key index in Array of Integers: "+index);
		} else {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}

Output:
D:\Java_Programs>javac TernarySearchTest.java
D:\Java_Programs>java TernarySearchTest 
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 5
Search key index in Array of Integers: 4

Java Program for Ternary Search using Recursive Method

import java.util.*;

class TernarySearchTest {
	// Ternary search method which search key in the array of integers
	// using recursive method
	static int ternarySearch(int[] numbers, int searchKey, int leftIndex, int rightIndex){          
	    if (rightIndex >= leftIndex){                                           
	        int midIndex1 = leftIndex + (rightIndex -leftIndex)/3;                  
	        int midIndex2 = rightIndex - (rightIndex - leftIndex)/3;                
	        if (numbers[midIndex1] == searchKey){                              
	            return midIndex1;                
	        }
	        if (numbers[midIndex2] == searchKey){                             
	            return midIndex2;                
	        }
	                                                                                
	        if (searchKey < numbers[midIndex1]){                               
	            return ternarySearch(numbers, searchKey, leftIndex, midIndex1-1 );
	        }
	        else if (searchKey > numbers[midIndex2]){                             
	            return ternarySearch(numbers, searchKey, midIndex2+1, rightIndex);
	        }
	        else{                                                                  
	            return ternarySearch(numbers, searchKey, midIndex1+1, midIndex2-1);
	        }
	    }
	    return -1;
	 }

	// Gets the Array of Integers
	static int[] getNumbers(Scanner sc){
		int[] numbers;
		System.out.print("Enter Number of Elements: ");
		int count = sc.nextInt();
		numbers = new int[count];
		System.out.println();
		System.out.println("Enter Array Numbers:");
		for (int i=0;i<count;i++){
			numbers[i]=sc.nextInt();
		}
		return numbers;
	}
	public static void main(String[] args){
		int[] numbers;
		Scanner sc = new Scanner(System.in);
		numbers = getNumbers(sc);
		System.out.println();
		System.out.print("Enter Search Key: ");
		int searchKey = sc.nextInt();
		sc.close();
		int leftIndex = 0;
		int rightIndex = numbers.length - 1;
		int index = ternarySearch(numbers, searchKey, leftIndex, rightIndex);
		// Prints the result, index -1 indicates that key is not found,
		//otherwise index location where key is found in array of integers.
		if (index >= 0){
			System.out.println("Search key index in Array of Integers: "+index);
		} else {
			System.out.println("Search key is not found in Array of Integers!");
		}
	}
}


Output:
D:\Java_Programs>javac TernarySearchTest.java
D:\Java_Programs>java TernarySearchTest 
Enter Number of Elements: 5

Enter Array Numbers:
1
2
3
4
5

Enter Search Key: 4
Search key index in Array of Integers: 3
Java Examples

GCD and Rational Number Java Program

Java Queue Program using exception

Java Stack Program using exception

Addition of three integers java program

Biggest of three integers java program

Fibonacci numbers java program

Arithmetic Operations Menu java program

Second Smallest Element In Array Java Program

Transpose Of A Matrix Java Program

Java Program to Display triangle of stars (*)

Java Programming Prints Product Tables

Java Program to Display triangle of numbers

Java Program to Get Current Date

Java Program to Find Character Vowel or Consonent

Java Program to Compute HCF and LCM

Java Program to Sum the Command Line Integer Arguments

Java Programm to Multiply the Command Line Integer Arguments

Java Program to Find Multiplication of Command Line Floating Point Numeric Arguments

Java Program to Check String Contains or Not

Java Program to Get Grade Description using Switch

Java Program for CSV File Reader

Java Program to Find Character Frequency Count in String using for each

Java Program to Find Min from Integer Array by Passing Array to Method

Java Program Linear Search

Binary Search Java Program

Ternary Search Java Program

Java Program to Generate Range of Numbers

Java Program to Generate Range of Characters

Java Program to Compute Square Root Value

Java Program to Check Number is Positive or Negative

Java Program to Check Number is Odd or Even

Java Program to Compute Plot Area

Java Program to Convert Number of Days into Years

Java Program to Check a Year is Leap Year, Century Year or Not

Java Program to Check a Character is Digit, Letter or neither digit nor letter

Java Program to Check a Number is Palindrome or not

Java Program to Sum Two Matrix

Java Program to Compute Power

Java Program to Check Number is an Armstrong Number or not

Java Program for Temperature Unit Conversions

Java Program to Generate Random Numbers in Specified Range

Java Program to Compute Sum of Digits and Product of Digits

Java Program to Compute Reverse Number

Java Programming Computes Factorial Value

Java Programming Checks Prime Number or not

Java Program to Compute Harmonic Series

Java Program Generate Floyd's Triangle

Java Program to Reverse String

Java Program to Check Palindrome String or not

Java Program to Open Notepad

Java Program to Search String using RegEx Pattern

Java Program to Search Word in String

Java Program to Get System Environment Variables

Java Program to Get IP Address of Server Name

Java Program for Arrays Sorting and Reverse using sort method

Java Program for Bubble Sorting

Java Program for Selection Sorting

Java Program for Insertion Sorting

Java Program for Merge Sorting

Java Program for Quick Sorting

Java Program for Counting Sort

Java Program for Radix Sorting

Java Program for Sorting Array of Strings

Java Program for String Characters Sorting

Java Program to Sum First N Numbers

Java Program to Product First N Numbers

Java Program to get URL details

Java Program to get URL HTML Content

Java Program to get URL details

Java Program to get URL HTML Content

Privacy Policy  |  Copyrightcopyright symbol2020 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^