Jump Search

1. Jump Search Algorithm
2. Jump Search Example
3. Jump Search Algorithm Implementation
4. Jump Search Algorithm Complexity

Jump Search is an interval searching algorithm. It is a relatively new algorithm that works only on sorted arrays. It tries to reduce the number of comparisons required than linear search by not scanning every single element like linear search. In jump search, the array is divided into m blocks. It searches the element in one block and, if the element is not present, then moves to the next block. When the algorithm finds the block containing the element, it uses the linear search algorithm to find the exact index. This algorithm is faster than linear search but slower than binary search.

Jump Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

Jump Search Example

Suppose we have the array: (1, 2, 3, 4, 5, 6, 7, 8, 9), and we want to find X - 7.

Since there are 9 elements, we have n as 9.

Jump Search Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

int jumpSearch(int arr[], int x, int n) {
  int m = sqrt(n);
  int i = 0;
  while (arr[min(m, n) - 1] < x) {
    i = m;
    m += sqrt(n);
    if (i >= n) return -1;
  }
  while (arr[i] < x) {
    i++;
    if (i == min(m, n)) return -1;
  }
  if (arr[i] == x) return i;

  return -1;
}

int main() {
  int n = 10;
  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 7;
  int result = jumpSearch(arr, x, n);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index " << result;
}

Jump Search Algorithm Complexity

Time Complexity

• Average Case

The jump sort algorithm runs n/m times where n is the number of elements, and m is the block size. Linear search requires m-1 comparisons making the total time expression n/m + m-1. The most optimal value of m minimizing the time expression is √n, making the time complexity n/√n + √n, i.e. √n. The time complexity of the Jump Search Algorithm is O(√n).

• Best Case

The best-case time complexity is O(1). It occurs when the element to be searched is the first element present inside the array.

• Worst-Case

The worst-case occurs when we do n/m jumps, and the last value we checked is greater than the element we are searching for, and m-1 comparisons are performed for linear search. The worst-case time complexity is O(√n).

Space Complexity

This algorithm’s space complexity is O(1) because it doesn’t require any data structure other than temporary variables.