Jump Search

Jump Search

 

Jump Search can be applied on sorted collections. It is better than Linear Search but worse than Binary Search.

 

Basically, in Jump Search, we divide the collection into equal m blocks and checks in which block desired element resides. Once we find the block, we perform the linear search.

 

Suppose we have given an array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; we need to find an element 8.

 

  1. we can divide this array into three equal blocks of three element. i.e. square root of array.length.
  2.  element 8 doesn’t fall into 1st block array[0 to 3], so, we can go for array[3 to 6] and then can go for 6-9
  3. since, desired element resides into block array[6-9], we can linearly search from array[6] to array[9]

 

Complexity of this algorithm is O(sq root of n) which is less than O(n) but greater than O(logn).

 
Here is the code.
 



package com.diaryreaders.datastructures.searching;
public class JumpSearch {
public static void main(String[] args) {
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };
int index = jumpSearch(array, 7);
System.out.println(index);
}
private static int jumpSearch(int[] array, int i) {
return jumpSearch(array, i, 0, (int) Math.sqrt(array.length));
}
private static int jumpSearch(int[] array, int element, int prev, int curr) {
if (curr > array.length - 1) {
curr = array.length - 1;
}
if (element > array[curr]) {
if (curr == array.length - 1) {
return -1;
}
return jumpSearch(array, element, curr, 2 * curr);
}
for (int i = prev; i <= curr; i++) {
if (array[i] == element) {
return i;
}
}
return -1;
}
}


 



Output:



 

No Comments Yet

Leave a Reply

Your email address will not be published.

Lorem ipsum dolor sit amet, consectetur a dipiscing elit. Vivamus leo ante,

FOLLOW US ON