1+ package src .main .java .com .search ;
2+
3+ public class JumpSearch {
4+
5+ /**
6+ * A jump search algorithm that finds the position of a key by moving over
7+ * fixed block ranges in a sorted array, and linear searches back on itself to
8+ * find it.
9+ *
10+ * Worst case time complexity: O(N^(1/2)) - square root n
11+ * Average case time complexity: O(N^(1/2)) - square root n
12+ * Worst case Space complexity: O(1)
13+ *
14+ * @param <T> This is any comparable type
15+ * @param arr This is the array where the element should be found
16+ * @param key This is the element to find in the array
17+ * @return The index of the key in the array
18+ */
19+ public <T extends Comparable <T >>int findIndex (T arr [],T key ) {
20+ return checkCondition (arr ,key ,arr .length );
21+ }
22+
23+ /**
24+ * @param arrLength The array's length
25+ * @return The index position of the key in the array
26+ */
27+ public <T extends Comparable <T >>int checkCondition (T arr [],T key ,int arrLength ) {
28+ int step = (int )Math .floor (Math .sqrt (arrLength ));// Find jump block
29+ int previous =0 ;// Find block where element is / or not present
30+
31+ // Use ternary operator to find if step or array length is min value
32+ // and then minus the min value by one
33+ int minVal = (step <arrLength ) ?step -1 :arrLength -1 ;
34+
35+ String arrayMinValIndexString =arr [minVal ].toString ();
36+ int arrayMinValIndexInt =Integer .parseInt (arrayMinValIndexString );
37+ String keyValueString =key .toString ();
38+ int keyValueInt =Integer .parseInt (keyValueString );
39+
40+ // Increment next step and previous step in block to find range block
41+ while (arrayMinValIndexInt <keyValueInt ) {
42+ previous =step ;
43+ step += (int )Math .floor (Math .sqrt (arrLength ));
44+ if (previous >=arrLength )
45+ return -1 ;
46+ minVal = (step <arrLength ) ?step -1 :arrLength -1 ;
47+ arrayMinValIndexString =arr [minVal ].toString ();
48+ arrayMinValIndexInt =Integer .parseInt (arrayMinValIndexString );
49+ }
50+ // Get key position in linear search
51+ int position =linearSearchBlock (arr ,key ,step ,previous ,keyValueInt ,arrLength ,minVal );
52+ return position ;
53+ }
54+
55+ /**
56+ * @param step The next block index in the array
57+ * @param previous The previous block index in the array
58+ * @param keyValueInt The key in the format of an integer
59+ * @param minVal The minimum value of either next step or array length
60+ * @return The index position of the key in the array
61+ */
62+ public <T extends Comparable <T >>int linearSearchBlock (T arr [],T key ,int step ,int previous ,int keyValueInt ,
63+ int arrLength ,int minVal ) {
64+
65+ // Linear search starting from previous block forwards.
66+ String arrayPositionString =arr [previous ].toString ();
67+ int arrayPositionValue =Integer .parseInt (arrayPositionString );
68+ while (arrayPositionValue <keyValueInt ) {
69+ // If in next block or end of array length, key not in array
70+ if (previous ==minVal )
71+ return -1 ;
72+ previous ++;
73+ // Update arrayPositionValue in iteration
74+ minVal = (step <arrLength ) ?step -1 :arrLength -1 ;
75+ arrayPositionString =arr [previous ].toString ();
76+ arrayPositionValue =Integer .parseInt (arrayPositionString );
77+
78+ }
79+ // If the key is found
80+ if (arrayPositionValue ==keyValueInt )
81+ return previous ;
82+ return -1 ;
83+ }
84+ }