jump search Algorithm
Jump search is an efficient searching algorithm that is particularly useful when applied to an ordered list of elements. It works by dividing the list into smaller sublists, or blocks, and then jumping between these blocks to determine the range within which the desired element may be located. The algorithm uses an optimal block size (usually determined by the square root of the list's length) to maximize the search efficiency. Once the appropriate block is identified, a linear search is performed within the block to find the desired element. This hybrid approach of combining a jump search with a linear search allows for faster search times compared to a linear search alone, while maintaining simplicity and ease of implementation.
The jump search algorithm begins by comparing the desired element with the first element of every block in the list. If the element is found to be less than or equal to the last element of a block, the search is narrowed down to that specific block. If the element is greater than the last element of a block, the algorithm jumps to the next block and repeats the process. If the element is not found in any of the blocks, it can be concluded that the element is not present in the list. Once the correct block is identified, a linear search is performed within that block to locate the exact position of the desired element. This combination of jumping between blocks and linear search within a block ensures that the jump search algorithm performs fewer iterations than a linear search, resulting in faster search times overall.
//
// C++ program to implement Jump Search
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/searches/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Bharat Reddy
// Github: @Bharat-Reddy
//
#include <bits/stdc++.h>
using namespace std;
int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] < x)
{
prev = step;
step += 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 == min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
int main()
{
int n,i;
cout<<"Eneter size of array : ";
cin>>n;
cout<<"Enter elements of array"<<endl;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
cout<<"Enter key to be searched : ";
int key;
cin>>key;
// Find the index of 'x' using Jump Search
int index = jumpSearch(a, key, n);
// Print the index where 'x' is located
cout << "\nNumber " << key << " is at index " << index;
return 0;
}
