Jump Search | Python3 code 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 code to test function ; Find the index of ' x ' using Jump Search ; Print the index where ' x ' is located
import math NEW_LINE def jumpSearch ( arr , x , n ) : NEW_LINE INDENT step = math . sqrt ( n ) NEW_LINE prev = 0 NEW_LINE while arr [ int ( min ( step , n ) - 1 ) ] < x : NEW_LINE INDENT prev = step NEW_LINE step += math . sqrt ( n ) NEW_LINE if prev >= n : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT while arr [ int ( prev ) ] < x : NEW_LINE INDENT prev += 1 NEW_LINE if prev == min ( step , n ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT if arr [ int ( prev ) ] == x : NEW_LINE INDENT return prev NEW_LINE DEDENT return - 1 NEW_LINE DEDENT arr = [ 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 ] NEW_LINE x = 55 NEW_LINE n = len ( arr ) NEW_LINE index = jumpSearch ( arr , x , n ) NEW_LINE print ( " Number " , x , " is ▁ at ▁ index " , " % .0f " % index ) NEW_LINE