Jump Search | Java program to implement Jump Search . ; Finding block size to be jumped ; Finding the block where element is present ( if it is present ) ; Doing a linear search for x in block beginning with prev . ; If we reached next block or end of array , element is not present . ; If element is found ; Driver program to test function ; Find the index of ' x ' using Jump Search ; Print the index where ' x ' is located
public class JumpSearch { public static int jumpSearch ( int [ ] arr , int x ) { int n = arr . length ; int step = ( int ) Math . floor ( Math . sqrt ( n ) ) ; int prev = 0 ; while ( arr [ Math . min ( step , n ) - 1 ] < x ) { prev = step ; step += ( int ) Math . floor ( Math . sqrt ( n ) ) ; if ( prev >= n ) return - 1 ; } while ( arr [ prev ] < x ) { prev ++ ; if ( prev == Math . min ( step , n ) ) return - 1 ; } if ( arr [ prev ] == x ) return prev ; return - 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 } ; int x = 55 ; int index = jumpSearch ( arr , x ) ; System . out . println ( " Number " ▁ + ▁ x ▁ + ▁ " is at index " + index); } }