Java Tutorial

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

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 Tutorial