Search

What is Jump search by ON August 18 2019

Jump search is like binary search which is search an element from sorted array.  It searches an element within block which is created as per the size list. If size of list is n then block size is √n. If element is not in current block then move to next block and performs leaner search to find the correct block. After getting correct block it performs linear search technique to find  the expected element from list.

Jump search using a linear and binary search technique.

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

int linearSearch(int arr[], int left, int right, int key)
{

    for( int i = left; i < right; i++ ) {
        // If key is match then return index of key.
        if ( arr[i] == key ) {
            return i;
        }
    }
    //If key is not exist in array.
    return -1;
}

int jumpSearch(int arr[],int arrayLength,int key) {
    int left  = 0;
    /*
    Here block size is equal to sqrt of the length
    Example = sqrt(14) =  3 that means the block size 3 here
    */
    int right = sqrt( arrayLength );

    //Check if It is not correct block then move to next block.
    while( arr[right] <= key && right < arrayLength ) {
        //Move left pointer to next block's first position.
        left = right;
        // Move the right pointer to next block's last position.
        right += sqrt( arrayLength );

        // Check if right exceeds then bound to the range
        if( right > arrayLength -1 ) {
            right = arrayLength;
        }
    }
  
    return linearSearch(arr,left,right,key);
}

int main() {

    // Array of elements.
    int arr[] = {1,4,7,11,16,19,23,28,30,31,40,78,105,201};

    // Length of array
    int arrayLength = sizeof( arr ) / sizeof( arr[0] );

    // Key that need to find in array.
    int key = 40;

    int index = jumpSearch( arr, arrayLength, key );

    if ( index != -1 ) {
        cout<<"Found element at position : "<<index<<endl;
    } else {
        cout<<"Given element is not exist in array"<<endl;
    }

    return 0;
}

Key points:

  • Jump search also called block search.
  • Always worked on a sorted list like binary search
  • The optimal size of a block to be jumped is (√ n).
  • The time complexity of the jump search is O(√ n).
  • The space complexity of the jump search is O(1).
  • Jump search lies between linear search and binary search according to its performance.
  • Jump search is better than a linear search if the list is sorted.
  • In worst-case scenario jump search jump, k/n where n is a number of elements and k is the size of the block.
  • The advantage over the binary is that a jump search only needs to jump backward once, while a binary can jump backward up to log n times.

References:-

https://en.wikipedia.org/wiki/Jump_search

RELATED POST


1. binary search

BY August 18 2019

2. linear search

BY August 18 2019
LEAVE A COMMENT

Leave a Reply

Your e-mail address will not be published. Required fields are marked *