Jump Search
Jump Search Algorithm in C++ (Complete Implementation)
IntermediateTopic: Sorting & Searching Programs
C++ Jump Search Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
#include <cmath>
using namespace std;
int jumpSearch(int arr[], int n, int key) {
// Calculate jump size
int step = sqrt(n);
int prev = 0;
// Find the block where element might be
while (arr[min(step, n) - 1] < key) {
prev = step;
step += sqrt(n);
if (prev >= n) {
return -1; // Element not found
}
}
// Perform linear search in the block
while (arr[prev] < key) {
prev++;
if (prev == min(step, n)) {
return -1; // Element not found
}
}
// If element is found
if (arr[prev] == key) {
return prev;
}
return -1; // Element not found
}
int main() {
int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Enter element to search: ";
cin >> key;
int result = jumpSearch(arr, n, key);
if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found in array" << endl;
}
return 0;
}Output
Sorted array: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 Enter element to search: 55 Element found at index: 10
Understanding Jump Search
Jump Search is a searching algorithm for sorted arrays that jumps ahead by fixed steps, then performs linear search in the identified block. Time Complexity: O(√n). Space Complexity: O(1). It's faster than linear search but slower than binary search. Optimal step size is √n.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.