# 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.

``````

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:

```
```