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

Jump Search

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.


\frac{n}{m} + m - 1
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


\frac{n}{ -m^{2} } + 1 = 0 \newline \newline  n = m^{2} \newline \newline  m = \sqrt{n}
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 🙂 .

CJavaPython
    
    
    

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 –

CJava
    
    

This optimised version has the following complexity –


\sqrt{N} + \sqrt{\sqrt{N}} + \sqrt{\sqrt{\sqrt{N}}} + ... + 1

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! 😀

Binary Search Algorithm

Hello people…! In this post we will discuss one of the most commonly used search algorithm, the Binary Search. In a search algorithm, we are given an element and a collection or a set of elements. If the given element exists in the given set, we must return where it is located, or otherwise, if it does not exist, our algorithm must be able to say it does not exist.

Binary Search Conditions

The given set must obey the following rules if we want to apply binary search –

  1. All pairs of elements in the given set must be comparable. Mathematically, this is called a totally ordered set.
  2. The given set must be sorted, in ascending or descending order.

Algorithm

Let’s say we are looking for 7 in an array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Binary search compares the middle element (here 5) and the element to be searched (here 7). So, 5 is less than 7. Binary search says, “Okay so 5 is less than 7, so don’t bother about the elements left of 5 because they are less than 5 anyway. It will never be equal to 7. Continue the same job with the right half instead!”. So, now we will look at the elements right of 5 only.

Now, let’s sat the middle element is 8. This time Binary Search says, “Elements right of 8 are more than 8, they will never be equal to 7, so neglect the elements right of 8, carry on with the elements left of 8.”

So if you analyse this carefully, we are cutting the size of elements we are supposed to look at by half for each step.

To implement this algorithm, we use 3 variables –

  • low – the lowest index of the searching range.
  • high – the highest index of the searching range.
  • mid – which is calculated by the formula below

binary-search-equation-1

 

 

Let us take the previous example array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This time let us search for 9, and this time we will find the middle element using the formula above.

binary search

Initially, low = 0 and high = 8, which gives mid = 4. The middle element is not 9, but 5 which is less than 9, so we might find 9 only to the right of 5. So, we will assign low = mid + 1.

binary search

Now, low = 5 and high = 8, which gives mid = 6. Value 7 is less than 9, so we search in the right half of 7. We do this by low = mid + 1. (If we wanted to search in the left half, say for 6 example, we would do high = mid – 1).

binary search

Even now, the middle element is less than the required element, so we must search in the right half. So we do low = mid + 1.

binary search

Now our middle element is equal to what we want, so we return this index! So basically Binary Search goes up to when there’s only one element left. If that remaining element is not the element we want, then we can claim that the given set does not contain it.

Just imagine if we were searching for 10 in the above case, we would go up to the last element and find that even the last element is not equal to 10, so we return a -1 or some value which denotes that the element is not found.

The reason the formula for calculating the middle element isn’t a simple average is to avoid an integer overflow error. If we try to calculate,

binary-search-equation-2

when low and high are close to maximum values of an integer, they can cause an integer overflow. This is why we use the formula mentioned above.

Complexity

We make one comparison per iteration. So what is the worst case? Worst case occurs when the element is not present in the given set. Then we need to iterate until we have one element left. At each iteration, we reduce the range by half, so how many iterations should we perform to reach a single element?

Binary Search complexity

It is log2 N! So the worst case complexity of binary search is O(log2 N). The best case would be if the middle element of the set is itself is the value we want to find, then, the complexity would be O(1).

Code

It is a fairly simple algorithm to code. Please try to write the code by yourself. If you get stuck, you can use my code below as a reference.

CC++JavaPython
    
    
    
    

You can code the binary search using recursion too. But I prefer the iterative version as it does not have the recursion overhead and it will not produce a stack overflow error for large arrays.

Keep practicing! Happy Coding! 🙂