|
| 1 | +packagecom.search; |
| 2 | + |
| 3 | +/** |
| 4 | + * A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function |
| 5 | + * The algorithm determines either that the minimum or maximum cannot be in the first third of the domain |
| 6 | + * or that it cannot be in the last third of the domain, then repeats on the remaining third. |
| 7 | + * <p> |
| 8 | + * Worst-case performanceΘ(log3(N)) |
| 9 | + * Best-case performanceO(1) |
| 10 | + * Average performanceΘ(log3(N)) |
| 11 | + * Worst-case space complexityO(1) |
| 12 | + */ |
| 13 | +publicfinalclassTernarySearch { |
| 14 | + |
| 15 | +/** |
| 16 | + * @param arr The **Sorted** array in which we will search the element. |
| 17 | + * @param value The value that we want to search for. |
| 18 | + * @return The index of the element if found. |
| 19 | + * Else returns -1. |
| 20 | + */ |
| 21 | +publicstatic <TextendsComparable<T>>intfind(T[]arr,Tvalue) { |
| 22 | +returnsearch(arr,value,0,arr.length -1); |
| 23 | + } |
| 24 | + |
| 25 | +/** |
| 26 | + * @param arr The **Sorted** array in which we will search the element. |
| 27 | + * @param key The value that we want to search for. |
| 28 | + * @param start The starting index from which we will start Searching. |
| 29 | + * @param end The ending index till which we will Search. |
| 30 | + * @return Returns the index of the Element if found. |
| 31 | + * Else returns -1. |
| 32 | + */ |
| 33 | +privatestatic <TextendsComparable<T>>intsearch(T[]arr,Tkey,intstart,intend) { |
| 34 | +if (start >end) { |
| 35 | +return -1; |
| 36 | + } |
| 37 | + |
| 38 | +intmid1 =start + (end -start) /3; |
| 39 | +intmid2 =start +2 * (end -start) /3; |
| 40 | + |
| 41 | +if (key.compareTo(arr[mid1]) ==0) { |
| 42 | +returnmid1; |
| 43 | + }elseif (key.compareTo(arr[mid2]) ==0) { |
| 44 | +returnmid2; |
| 45 | + } |
| 46 | +elseif (key.compareTo(arr[mid1]) <0) { |
| 47 | +returnsearch(arr,key,start, --mid1); |
| 48 | + } |
| 49 | +elseif (key.compareTo(arr[mid2]) >0) { |
| 50 | +returnsearch(arr,key, ++mid2,end); |
| 51 | + } |
| 52 | +else { |
| 53 | +returnsearch(arr,key,mid1,mid2); |
| 54 | + } |
| 55 | + } |
| 56 | + |
| 57 | +} |
