Jump Search

In this tutorial, we'll learn about Jump Search, a simple Search Algorithm. Although it isn't widely used, it is still good to understand what it is and how to implement it, just in case you ever need to use it.

What is a Jump Search?

A Jump Search is a simple and quick Search Algorithm. It searches for elements within an array, also known as a list, and returns the index of a target element. It works by skipping through the sorted list by a certain number of jumps, and then looks to see if the element it is at is higher than the target element. If it is, then it will run a Linear Search backwards until it find the target element.

Jump Search Implementation

A Jump Search is actually very easy to implement. Below is the implementation of a Jump Search, copy it down first, and then we will break it down:


import math

def jump_search(arr, x):
    """This function performs a simple Jump Search on arr and searches for x withen the array.."""
    n = len(arr)
    step = math.floor(math.sqrt(n))
    prev = 0
    while arr[int(min(step, n)-1)] < x:
        prev = step
        step += math.floor(math.sqrt(n))
        if prev >= n:
            return -1
    while arr[int(prev)] < x:
        prev += 1
        if prev == min(step, n):
            return -1
    if arr[int(prev)] == x:
        return prev
         
    return -1

Running the Code

The code is written in a simple function. It performs a Jump Search on the array, arr, and finds the first occurence of the value of x. If the element is not found, the program returns -1. Otherwise, it returns the index where x is found.

Code Breakdown

The code for a Jump Search is very simple. On the first line, we define a function with

def jump_search(arr, x):

On the next line, we have a multi-line string. When you put a multi-line string on the line right after declaring a function, we call it a doc-string, which tells the developer a little bit about the function. Then, we declare some variables for our function:


n = len(arr)
step = math.sqrt(n)
prev = 0

n is the length of the array that we are going to search, and we use it for checking if we have jumped through the entire list but didn't find it. If that happens, then we will break the function and return -1.

Then, we have the code that runs the Jumps:


while arr[int(min(step, n)-1)] < x:
    prev = step
    step += math.floor(math.sqrt(n))
    if prev >= n:
        return -1

We run this code while the element we are at is less than the target element. Once it is greater than the target element, we break out of the loop. If we ever jump to a position greater than the length of the list, we will break out of the function and return -1.

Then, we perform a Linear Search backwards until we find the target element.


while arr[int(prev)] < x:
    prev += 1
    if prev == min(step, n):
        return -1

Once we hit the previous jump index, we break and check if we found the index of x. If we did, we just return the index where we found x.

Finally, on the last line, we have return -1. This will just return -1 if the target is not found.