Home » Algorithms

Jump Search Implementation using C++



In this article, we are going to learn what is Jump search, and how to implement it using C++ program?
Submitted by Aleesha Ali, on February 08, 2018

Jump search is a Searching algorithm and its efficiency lies between linear search and binary search.

Here, we search or find a particular element with the help of step size means we search a particular element by jumping or skipping the in-between values according to the step size given by the user if a particular element is still not found then this algorithm will follow simple linear search on previous elements.

For applying this​​ algorithm elements must be in sorted order means ascending or descending.

Complexity:

    
    sqrt(n) or (√n).
    Sqrt = SquareRoot.
    

Implementation of Jump Search using C++

//Implementation of jump search using c++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int jumpSearchProg(vector <int> arr, int noToSearch, int ArrayLim)
{
	int previous = 0;
	int step = sqrt(ArrayLim);
	//Step to skip elements for jumping

	while (arr[min(step,ArrayLim)-1] < noToSearch)
	{
		previous = step;
		step += sqrt(ArrayLim);
		if(previous >= ArrayLim) return -1;
	}

	/*Applying linear Search and starting from the previous elements*/
	while (arr[previous] < noToSearch)
	{
		previous++;
	/*If element has not found yet then it means element is not present in the array*/
		if (previous == min(step, ArrayLim)) return -1;
	}
	// if we found the element then

	if (arr[previous] == noToSearch)
		return previous;

	return -1;
}

//Start of main
int main()
{
	int n,NoToSr;
	cout<<"Enter the length of the array:"<<endl;
	cin>>n;
	vector<int> arr(n);

	cout<<"Enter the elements of the array"<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}

	cout<<"Enter the number to be searched:"<<endl;
	cin>>NoToSr;

	//function calling
	int result = jumpSearchProg(arr, NoToSr, n);

	//displayin foud number
	cout<<"Number = "<<NoToSr<<"is found at index = "<<result<<endl;
	return 0;
}

Output

Jump search implementation using C++ - Output






Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.