Algorithm - Skip Search

For example, suppose we have an array arr[] of size n and block (to be jumped) of size m. Then we search the indices arr[0], arr[m], arr[2m]... ..arr[km] and so on. Once we find the interval (arr [km]

We consider the following array: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610). The length of the array is 16. A skip search will find 55 in the following steps, assuming the block size to be skipped is 4.

Step 1: Jump from index 0 to index 4;
Step 2: Jump from index 4 to index 8;
Step 3: Jump from index 8 to index 16;
Step 4: Since the element at index 16 is greater than 55, we will go back one step to index 9.
Step 5: Perform a linear search from index 9 to get element 55.
What is the optimal block size to skip?
In the worst case we have to do n/m jumps and do m-1 comparisons with a linear search if the last checked value is greater than the element being searched. Therefore, the worst case total number of comparisons will be ((n/m)m-1). When m =√n, the value of the function ((n/m) m-1) will be the minimum value. Therefore, the best step size is m = √n.

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>Output: </p>
<p>Number 55 is at index 10</p>
<p>Time complexity: O(√n)<br>
Auxiliary space: O(1)</p>
<p><strong>Notice:</strong></p>
<p>This search only works on sorted arrays. <br>
The optimal size of chunks to skip is O(√n). This makes the jump search O(√n) time complexity. <br>
The time complexity of skip search is between linear search ((O(n))) and binary search (O(Log n)).<br>
Binary search is better than jump search, but jump search has the advantage that we traverse only once (binary search may require at most 0 (Log n) jumps, considering the element being searched is the smallest element or less than the smallest). Therefore, in systems where jumping back is expensive, we use Jump Search. </p></bits>

The above is the detailed content of Algorithm - Skip Search. For more information, please follow other related articles on the PHP Chinese website!