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 Java program
Ternary search program in Java using recursive calls.
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
You may also like-
