{"id":2840,"date":"2016-11-10T23:27:28","date_gmt":"2016-11-10T17:57:28","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=2840"},"modified":"2023-11-19T07:52:35","modified_gmt":"2023-11-19T07:52:35","slug":"jump-search-algorithm","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2016\/11\/10\/jump-search-algorithm\/","title":{"rendered":"Jump Search Algorithm"},"content":{"rendered":"\n

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(\u221aN) 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(\u221aN) worst case complexity? You would be banging your head to cook up a new algorithm \ud83d\ude1b . Anyways, it’s fun learning new stuff, isn’t it?<\/p>\n\n\n\n

Algorithm<\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

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].<\/p>\n\n\n\n

\"Jump<\/a><\/figure>\n\n\n\n

Sound too boring? Here’s where things get interesting! How will we know the most optimal value of the jump size?<\/p>\n\n\n\n

Optimal Jump Size<\/h2>\n\n\n\n

If we try to write down the complexity of the algorithm we described above.<\/p>\n\n\n\n

\" \frac{n}{m} + m - 1 \"<\/p>\n\n\n\n

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<\/p>\n\n\n\n

\" \frac{n}{ -m^{2} } + 1 = 0 \newline \newline n = m^{2} \newline \newline m = \sqrt{n} \"<\/p>\n\n\n\n

So, the optimal jump size is \u221aN.<\/p>\n\n\n\n

Code<\/h2>\n\n\n\n

It is a pretty simple algorithm to code. Try it by yourself. You can refer to my code below if you get stuck \ud83d\ude42 .<\/p>\n\n\n

C<\/span>C++<\/span>Java<\/span>Python<\/span><\/div>
\n