Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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

12  {
13  // Finding block size to be jumped
14  int step = std::sqrt(n);
15 
16  // Finding the block where element is
17  // present (if it is present)
18  int prev = 0;
19  while (arr[std::min(step, n) - 1] < x) {
20  prev = step;
21  step += std::sqrt(n);
22  if (prev >= n)
23  return -1;
24  }
25 
26  // Doing a linear search for x in block
27  // beginning with prev.
28  while (arr[prev] < x) {
29  prev++;
30 
31  // If we reached next block or end of
32  // array, element is not present.
33  if (prev == std::min(step, n))
34  return -1;
35  }
36  // If element is found
37  if (arr[prev] == x)
38  return prev;
39 
40  return -1;
41 }
Here is the call graph for this function:
std::sqrt
T sqrt(T... args)
std::min
T min(T... args)
std::prev
T prev(T... args)