C++
#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
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:
- Sorted array: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
- Search for: 55
- Result: Element found at index 10
Jump Search jumps ahead by √n steps, then performs linear search in the block where the element might be located.
2. Header Files Used
-
#include <iostream>
- Provides cout and cin for input/output operations.
-
#include <cmath>
- Provides sqrt() function to calculate square root for optimal step size.
3. Understanding Jump Search
Algorithm Concept:
- Divide array into blocks of size √n
- Jump ahead by √n steps
- When element is found to be between two jumps, perform linear search in that block
- Combines benefits of linear and binary search
Visual Example:
Array: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] n = 16, step = √16 = 4
Jump 1: Check arr[3] = 2 < 55 → continue Jump 2: Check arr[7] = 13 < 55 → continue Jump 3: Check arr[11] = 89 > 55 → found block [8, 11] Linear search in block: arr[8]=21, arr[9]=34, arr[10]=55 → found!
4. Function: jumpSearch()
int jumpSearch(int arr[], int n, int key) { 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;
}
}
// 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;
}
How it works:
- Calculate step size: √n
- Jump ahead until block containing key is found
- Perform linear search in identified block
- Return index if found, -1 otherwise
5. Step-by-Step Algorithm
Step 1: Calculate Step Size
- step = √n (optimal block size)
- Example: n = 16 → step = 4
Step 2: Find Block
- Jump ahead by step size
- Check arr[min(step, n) - 1] with key
- If key is larger, continue jumping
- If key is smaller or equal, block found
Step 3: Linear Search in Block
- Start from prev (beginning of block)
- Search linearly until key found or block end
- Check each element sequentially
Step 4: Return Result
- If arr[prev] == key: return index
- If block exhausted: return -1
6. Understanding Step Size
Why √n?
- Optimal balance between jump size and block size
- Too large: many elements to search linearly
- Too small: too many jumps
- √n minimizes total comparisons
Example (n = 16):
- step = √16 = 4
- Number of blocks: 16/4 = 4 blocks
- Maximum linear search: 4 elements per block
- Total worst case: 4 jumps + 4 comparisons = 8 operations
7. Time and Space Complexity
Time Complexity: O(√n)
- Jump phase: O(√n) - at most √n jumps
- Linear search phase: O(√n) - at most √n elements in block
- Total: O(√n)
Space Complexity: O(1)
- Only uses constant extra space
- Variables: step, prev
- No additional arrays needed
8. When to Use Jump Search
Best For:
- Sorted arrays
- When Binary Search is not available
- When you want better than Linear Search
- Uniformly distributed data
Not Recommended For:
- Unsorted arrays (must sort first)
- Very large arrays (Binary Search is better)
- When O(log n) is required
- Performance-critical applications
9. Comparison with Other Search Algorithms
vs Linear Search:
- Faster: O(√n) vs O(n)
- Still requires sorted array
- More complex implementation
vs Binary Search:
- Slower: O(√n) vs O(log n)
- Simpler implementation
- Better for small arrays
10. Important Considerations
Array Must Be Sorted:
- Jump Search only works on sorted arrays
- Sort array first if unsorted
- Same requirement as Binary Search
Step Size Calculation:
- Optimal: √n
- Can be adjusted based on data distribution
- Fixed step size (unlike Interpolation Search)
Block Boundaries:
- min(step, n) prevents array out-of-bounds
- Important for arrays where n is not perfect square
11. return 0;
This ends the program successfully.
Summary
- Jump Search jumps ahead by √n steps, then searches linearly in identified block.
- Time complexity: O(√n) - faster than Linear Search, slower than Binary Search.
- Space complexity: O(1) - only uses constant extra space.
- Requires sorted array - same as Binary Search.
- Optimal step size is √n for balanced performance.
- Combines jumping and linear searching for efficiency.
- Best for sorted arrays when Binary Search is not preferred.
- Understanding Jump Search demonstrates intermediate searching techniques.
This program is fundamental for learning intermediate search algorithms, understanding block-based searching, and preparing for advanced searching methods in C++ programs.