Jump Search Algorithm

Hello, people…! In this post, we will discuss a new search algorithm, Jump Search, which searches for an element in a sorted array in O(√N) time. It is slower than binary search, then why learn it? What if the interviewer purposely asks you to write a search algorithm with O(√N) worst case complexity? You would be banging your head to cook up a new algorithm 😛 . Anyways, it’s fun learning new stuff, isn’t it?

Algorithm

Imagine you are given a sorted array, and you are applying linear search to find a value. Jump Search is an improvement to this scenario. Instead of searching one-by-one, we search k-by-k. Let’s say we have a sorted array A, then jump search will look at A[1], A[1 + k], A[1 + 2k], A[1 + 3k] … and so on.

As we keep jumping, we keep a note of the previous value and its index. Once we get a situation where A[i] < searchValue < A[i + k], then it means the value we want is in between the previous jump ends. So now we could simply perform a linear search between that A[i] and A[i + k].

Sound too boring? Here’s where things get interesting! How will we know the most optimal value of the jump size?

Optimal Jump Size

If we try to write down the complexity of the algorithm we described above.

Now, let’s see for which value of ‘m’ does this expression have a minimum. To do this we differentiate with respect to ‘m’ and equate it to 0

So, the optimal jump size is √N.

Code

It is a pretty simple algorithm to code. Try it by yourself. You can refer to my code below if you get stuck 🙂 .

Faster Jump Search

How can we make this version of jump search faster? A few people might have guessed it by now! 😉 In the above algorithm, once we find the jump ends which contains the value we need, we are performing a linear search. But we could perform another jump search between these two jump ends! And then recursively perform jump search until we are left with only one element.

Implementing this version is more challenging. Firstly, you need to modify your above method to something which looks like this –

public Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
    // return jump ends if condition meets
    // return null or a -1 otherwise
}

We must return the i and j between which the value is found or return null. And then call this from another method jumpSearch() which keeps calling jumpSearchUtil() until the jump interval has only 2 elements or it returns a null. We will need to return 2 values, the left end and the right end of the jump. So, we will use a structure in C, or a class in Java.

Try to code this version of Jump Search algorithm. If you get stuck, you can use my code below as a reference –

This optimised version has the following complexity –

This is still O(√N) in the worst case. But it is much faster because, in the previous version, the complexity was √N + √N, which made it O(√N), but here the additional terms have very low values.

I hope you’ve understood about the jump search algorithm. If you did, let me know by commenting! Keep practising! Happy Coding! 😀