forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTernarySearch.java
More file actions
74 lines (66 loc) · 2.4 KB
/
Copy pathTernarySearch.java
File metadata and controls
74 lines (66 loc) · 2.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Scanner;
public class TernarySearch{
/**
* @param arr The **Sorted** array in which we will search the element.
* @param value The value that we want to search for.
* @return The index of the element if found.
* Else returns -1.
*/
public static int ternarySearch(int[] arr, int value){
return ternarySearch(arr, value, 0, arr.length - 1);
}
/**
* @param arr The **Sorted** array in which we will search the element.
* @param key The value that we want to search for.
* @param start The starting index from which we will start Searching.
* @param end The ending index till which we will Search.
* @return Returns the index of the Element if found.
* Else returns -1.
*/
public static int ternarySearch(int[] arr, int key, int start, int end) {
if (start > end){
return -1;
}
/* First boundary: add 1/3 of length to start */
int mid1 = start + (end - start) / 3;
/* Second boundary: add 2/3 of length to start */
int mid2 = start + 2 * (end - start) / 3;
if (arr[mid1] == key) {
return mid1;
}
else if (arr[mid2] == key) {
return mid2;
}
/* Search the first (1/3) rd part of the array.*/
else if (key < arr[mid1]) {
return ternarySearch(arr, key, start, mid1 - 1);
}
/* Search 3rd (1/3)rd part of the array */
else if (key > arr[mid2]) {
return ternarySearch(arr, key, mid2 + 1, end);
}
/* Search middle (1/3)rd part of the array */
else {
return ternarySearch(arr, key, mid1, mid2);
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter number of elements in the array");
int n = s.nextInt();
int arr[] = new int[n];
System.out.println("Enter the elements of the Sorted array");
for (int i= 0; i < n; i++){
arr[i] = s.nextInt();
}
System.out.println("Enter element to search for : ");
int k = s.nextInt();
int ans = ternarySearch(arr, k);
if (ans == -1) {
System.out.println(" The element is not present in the array.");
}
else {
System.out.println("The element is present at the position " + (ans+1));
}
}
}