Jump Search in C++

Jump Search Algorithm in C++ (Complete Implementation).

IntermediateSorting & Searching ProgramsExample 12 of 13

jump-search.cpp

1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int jumpSearch(int arr[], int n, int key) {
6    // Calculate jump size
7    int step = sqrt(n);
8    int prev = 0;
9    
10    // Find the block where element might be
11    while (arr[min(step, n) - 1] < key) {
12        prev = step;
13        step += sqrt(n);
14        if (prev >= n) {
15            return -1;  // Element not found
16        }
17    }
18    
19    // Perform linear search in the block
20    while (arr[prev] < key) {
21        prev++;
22        if (prev == min(step, n)) {
23            return -1;  // Element not found
24        }
25    }
26    
27    // If element is found
28    if (arr[prev] == key) {
29        return prev;
30    }
31    
32    return -1;  // Element not found
33}
34
35int main() {
36    int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
37    int n = sizeof(arr) / sizeof(arr[0]);
38    int key;
39    
40    cout << "Sorted array: ";
41    for (int i = 0; i < n; i++) {
42        cout << arr[i] << " ";
43    }
44    cout << endl;
45    
46    cout << "Enter element to search: ";
47    cin >> key;
48    
49    int result = jumpSearch(arr, n, key);
50    
51    if (result != -1) {
52        cout << "Element found at index: " << result << endl;
53    } else {
54        cout << "Element not found in array" << endl;
55    }
56    
57    return 0;
58}

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

What's going on

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.

Header Files Used

1.#include <iostream>

Provides cout and cin for input/output operations.

2.#include <cmath>

Provides sqrt() function to calculate square root for optimal step size.

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!

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;

}

1// Find the block where element might be

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

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

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

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

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

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

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

return 0;

This ends the program successfully.

PreviousBinary Search (Recursive)NextInterpolation Search