jump_search.cpp File Reference

C++ program to implement Jump Search More...

#include <algorithm>
#include <cmath>
#include <iostream>

Include dependency graph for jump_search.cpp:

Functions
int	jumpSearch (int arr[], int x, int n)
int	main ()

Detailed Description

C++ program to implement Jump Search

Function Documentation

jumpSearch()

int jumpSearch	(	int	arr[],
		int	x,
		int	n
	)

jump search implementation

                                        {
    // Finding block size to be jumped
    int step = std::sqrt(n);
 
    // Finding the block where element is
    // present (if it is present)
    int prev = 0;
    while (arr[std::min(step, n) - 1] < x) {
        prev = step;
        step += std::sqrt(n);
        if (prev >= n)
            return -1;
    }
 
    // Doing a linear search for x in block
    // beginning with prev.
    while (arr[prev] < x) {
        prev++;
 
        // If we reached next block or end of
        // array, element is not present.
        if (prev == std::min(step, n))
            return -1;
    }
    // If element is found
    if (arr[prev] == x)
        return prev;
 
    return -1;
}

Here is the call graph for this function:

main()

int main

(

void

)

           {
    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]);
 
    // Find the index of 'x' using Jump Search
    int index = jumpSearch(arr, x, n);
 
    // Print the index where 'x' is located
    std::cout << "\nNumber " << x << " is at index " << index;
    return 0;
}