Jump Search | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int jumpSearch ( int arr [ ] , int x , int n ) { int step = sqrt ( n ) ; int prev = 0 ; while ( arr [ min ( step , n ) - 1 ] < x ) { prev = step ; step += sqrt ( n ) ; if ( prev >= n ) return -1 ; } while ( arr [ prev ] < x ) { prev ++ ; if ( prev == min ( step , n ) ) return -1 ; } if ( arr [ prev ] == x ) return prev ; return -1 ; } int main ( ) { int arr [ ] = { 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 } ; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int index = jumpSearch ( arr , x , n ) ; cout << " Number " ▁ < < ▁ x ▁ < < ▁ " is at index " return 0 ; }