Jump Search
Jump Search Algorithm in C++ (Complete Implementation)
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;
}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
This program teaches you how to implement the Jump Search algorithm in C++. Jump Search is a searching algorithm for sorted arrays that works by jumping ahead by fixed steps, then performing a linear search in the identified block. It's faster than Linear Search but slower than Binary Search, making it a middle-ground option.
---
1. What This Program Does
The program searches for an element in a sorted array using Jump Search. For example:
Jump Search jumps ahead by √n steps, then performs linear search in the block where the element might be located.
---
2. Header Files Used
---
3. Understanding Jump Search
Algorithm Concept
:
Visual Example
:
n = 16, step = √16 = 4
---
4. Function: jumpSearch()
int jumpSearch(int arr[], int n, int key) {
int step = sqrt(n);
int prev = 0;
while (arr[min(step, n) - 1] < key) {
prev = step;
step += sqrt(n);
if (prev >= n) {
return -1;
}
}
// Perform linear search in the block
while (arr[prev] < key) {
prev++;
if (prev == min(step, n)) {
return -1;
}
}
if (arr[prev] == key) {
return prev;
}
return -1;
}
// Find the block where element might beHow it works
:
---
5. Step-by-Step Algorithm
Step 1: Calculate Step Size
Step 2: Find Block
Step 3: Linear Search in Block
Step 4: Return Result
---
6. Understanding Step Size
Why √n?
Example
(n = 16):
---
7. Time and Space Complexity
Time Complexity
: O(√n)
Space Complexity
: O(1)
---
8. When to Use Jump Search
Best For
:
Not Recommended For
:
---
9. Comparison with Other Search Algorithms
vs Linear Search
:
vs Binary Search
:
---
10. Important Considerations
Array Must Be Sorted
:
Step Size Calculation
:
Block Boundaries
:
---
11. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for learning intermediate search algorithms, understanding block-based searching, and preparing for advanced searching methods in C++ programs.
Let us now understand every line and the components of the above program.
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.
Practical Learning Notes for Jump Search
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.