JIYIK CN >

Skip search is a range search algorithm. It is a relatively new algorithm that works only on sorted arrays. It tries to reduce the number of comparisons required compared to linear search by not scanning every element like linear search. In skip search, the array is divided into mblocks. It searches for an element in a block and if the element is not present, it moves to the next block. When the algorithm finds a block containing an element, it uses a linear search algorithm to find the exact index. This algorithm is faster than linear search but slower than binary search.

Jump Search Algorithm

Suppose we have an unsorted array A[]containing nelements and we want to find an element X.

• Starting from the first element, set i to 0 and the block size m to √n.
• When A[min(m,n)-1]<X and i<n.
  • Set i to m, and increment m by √n.
• If i >= n return -1.
• When A[i]< X, do the following.
  • Increment i
  • If i is equal to min(m,n) return -1.
• If A[i] == X, return i.
• Otherwise, returns -1.

Jump Search Example

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

Since there are 9 elements, we nset to 9.

1. Let i be 0 and m be √9, which is 3.
2. A[2] is smaller than X. Let i be 3 and m be 6.
3. A[5] is smaller than X. Let i be 6 and m be 9.
4. A[8] equals X. Break out of the loop.
5. i as 6 is less than n.
6. A[6] == 7, break out of the loop.
7. Since A[6]=7, 6 is returned.

Implementation of the Jump Search Algorithm

#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;
}

Complexity of jump search algorithm

Time Complexity

• Average situation

The skip sort algorithm runs n/mtimes, where nis the number of elements and mis the block size. Linear search requires m-1times comparisons, so that the total time expression is . The optimal value of that n/m+m-1minimizes the time expression is , so that the time complexity is , that is . The time complexity of the skip search algorithm is .m√nn/√n+√n√nO(√n)

• Best Case

The best case time complexity is O(1). This occurs when the element being searched is the first element in the array.

• Worst case scenario

The worst case happens n/mwhen we make a jump, and the last value we check is greater than the element we are searching for, m-1so the comparison is a linear search. The worst case time complexity is O(√n).

Space complexity

The space complexity of this algorithm is O(1), since it does not require any data structures except temporary variables.