Friday, 10 March 2017

Explanation of Jump Search

 Jump Search Algorithm is also known as block search Algorithm. Like Binary search, sorted list or array can only use Jump search. In jump search algorithm we don't scan every element in array or list till we find the desired element as we do in linear search algorithm.

In Jump search algorithm we just check the element at index R, if it is less than the element to be found then we compare it with element at index R+R. This process is continued until element at index R will become equal to or greater than the element to be found.

Obviously, it is a good practice to use a fixed size step. Actually when the step is 1 then the Algorithm is traditional linear search. The question is that what should be the length of the step and is there any relation between the size of the list or array. And ofcourse there is a relation and i.e
        
R=√n, where n is the size of array or list.

Now question is that why we are taking the  R=√n. It's simple because this is the optimal step.

Proof:
       In the worst case scenarion, we will do n/R jumps and if the last checked value is greater than the desired value, then we at most more k-1 comparison.

       Therefore, total iterations will be = n/R + R - 1

       Let 'y' be the function of 'R'

       Now,      y = n/R + R - 1
                 Taking first derivative w.r.t R

                 dy/dR = -(n/R^2) + 1.......... equation 2

                 puting first derivative '0'

                 R=√n

       Now take second derivative of equation 2 w.r.t R, and you will know why R=√n is the optimal jump.

Example:
     


Points to Remember:

1. It works only on sorted arrays or list.

2. The Optimal size of a block to be jumped is sqrt(n) and this makes the Time complexity of the jump search O(sqrt(n)).

3. Jump search is better than Linear Search and worse than Binary Search.

4. Jump search has an advantage that we traverse back only once while Binary search may require up to O(log n) jumps.

5. Moreover, If we once know the interval where the value is we can improve it by applying jump search again.

       Implementation of the Jump Search in C
      



EmoticonEmoticon