Jump Search Algorithm

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Algorithm
Complexity
Implementations
Applications
Discussions

Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Algorithm

The steps involved in this algorithm are:
(Block size: B and list size: N; list is sorted in ascending order)

Step 1: Start from index 1
Step 2: Jump head by B elements. Current position = Current position + B. If position is out of element list, set current position to last position.
Step 3: If element at current position < target element, then do Linear Search on element from position current position -B to current position else go to step 2. If current position is last position, go to step 4.
Step 4: Exit. Element not found.

** How is the perfect block size √N? **

Consider the list to be of size N and Block size of size B.

In the worst case, we have to do N/B jumps and if the element is not present, we perform B-1 comparisons. Therefore, the total number of comparisons in the worst case will be ((N/B) + B-1). The value of the function ((N/B) + B-1) will be minimum when B = √N.

Therefore, the best block size is B = √N.

Complexity

Worst case time complexity: O(√N)
Average case time complexity: O(√N)
Best case time complexity: O(1)
Space complexity: O(1)

Implementations

Implementation of Linear search algorithm in 16 languages that includes C, C++, Java, Go, JavaScript, PHP, Python, Rust and Swift.

C
C++
Java
Go
JavaScript
PHP
Python
Rust
Swift

Tab 1


#include <stdio.h>
#include <math.h>
#define MAX 100
int find_element(int element);
int arr[MAX],n;
int main()
{
   int i,element,result;
   printf("\nEnter the number of elements: ");
   scanf("%d",&n);
   printf("\nEnter the elements of array: \n");
   for(i=0;i<n;i++)
   {
         scanf("%d",&arr[i]);
   }
      printf("\n\nEnter the element you want to search: ");
      scanf("%d",&element);
      result=find_element(element);
      if(result==-1)
      {
            printf("\nElement is not found in the array !\n");
      }
      else
      {
            printf("\nElement %d is present at position %d",element,result);
      }
      return 0;
}
int find_element(int element)
{
   int jump_step,prev=0;
   jump_step=floor(sqrt(n));
   /* Finding block in which element lies, if it is present */
   while(arr[prev]<element)
   {
       if(arr[jump_step]>element || jump_step>=n)
       {
            break;
       }
       else
       {
                prev=jump_step;
                jump_step=jump_step+floor(sqrt(n));
       }
   }
   /*Finding the element in the identified block */
   while(arr[prev]<element)
   {
        prev++;
   }
   if(arr[prev]==element)
   {
        return prev+1;
   }
   else
   {
        return -1;
   }
}

Tab 2


/*

Part of Cosmos by OpenGenus Foundation

jump search synopsis

warning: in order to follow the convention of STL, the interface is [begin, end) !!!

namespace jump_search_impl

{

template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type,

typename _Compare>

_Random_Access_Iter

jumpSearchImpl(_Random_Access_Iter begin,

_Random_Access_Iter end,

_Tp const &find,

_Compare comp,

std::random_access_iterator_tag);

} // jump_search_impl

template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type,

typename _Compare>

_Random_Access_Iter

jumpSearch(_Random_Access_Iter begin, _Random_Access_Iter end, _Tp const &find, _Compare comp);

template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type>

_Random_Access_Iter

jumpSearch(_Random_Access_Iter begin, _Random_Access_Iter end, _Tp const &find);

*/
include <functional>
include <cmath>
namespace jump_search_impl

{

template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type,

typename _Compare>

_Random_Access_Iter

jumpSearchImpl(_Random_Access_Iter begin,

_Random_Access_Iter end,

_Tp const &find,

_Compare comp,

std::random_access_iterator_tag)

{

if (begin != end)

{

auto dist = std::distance(begin, end);

auto sqrtDist = static_cast<size_t>(std::sqrt(dist));

auto curr = begin;

// 1. Finding the block where element is

while (curr < end && comp(*curr, find))

std::advance(curr, sqrtDist);

if (curr != begin)

std::advance(curr, -sqrtDist);

// 2. Doing a linear search for find in block

while (curr < end && sqrtDist-- > 0 && comp(*curr, find))

std::advance(curr, 1);

// 3. If element is found

if (!comp(*curr, find) && !comp(find, *curr))

return curr;

}

return end;

}

} // jump_search_impl

template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type,

typename _Compare>

_Random_Access_Iter

jumpSearch(_Random_Access_Iter begin, _Random_Access_Iter end, _Tp const &find, _Compare comp)

{

auto category = typename std::iterator_traits<_Random_Access_Iter>::iterator_category();
return jump_search_impl::jumpSearchImpl(begin, end, find, comp, category);

}
template<typename _Random_Access_Iter,

typename _Tp = typename std::iterator_traits<_Random_Access_Iter>::value_type>

_Random_Access_Iter

jumpSearch(_Random_Access_Iter begin, _Random_Access_Iter end, _Tp const &find)

{

return jumpSearch(begin, end, find, std::less<_Tp>());

}

Tab 3


public class JumpSearch {
	// Java program to implement Jump Search.
	public static int SearchJump(int[] arr, int x) {
		int n = arr.length;
		// block size through which jumps take place
		int step = (int) Math.floor(Math.sqrt(n));
		// search in the block
		int prev = 0;
		while (arr[Math.min(step, n) - 1] < x) {
			prev = step;
			step += (int) Math.floor(Math.sqrt(n));
			if (prev >= n)
				return -1;
		}
		// Doing a linear search for x in block
		while (arr[prev] < x) {
			prev++;
			/*
			 * If we reached next block or end of array, element is not present.
			 */
			if (prev == Math.min(step, n))
				return -1;
		}
		// If element is found
		if (arr[prev] == x)
			return prev;
		// element not found
		return -1;
	}
	// Driver program to test function
	public static void main(String[] args) {
		int arr[] = { 0, 1, 1, 2, 3, 5, 9, 13, 21, 34, 55, 89, 145, 237, 377, 610 };
		int x = 55;
		// Find the index of 'x' using Jump Search
		int index = SearchJump(arr, x);
		// Print the index where 'x' is located
		if (x != -1)
			System.out.println("Number " + x + " is found at index " + index);
		else {
			System.out.println("Number " + x + " not found");
		}
}

}

Tab 4


package main
import (
	"fmt"
	"math"
)
// Part of Cosmos by OpenGenus Foundation
func jumpSearch(arr []int, x int) int {
	var left, right int
	length := len(arr)
	jump := int(math.Sqrt(float64(length)))
	for left < length && arr[left] >= x {
		right = min(length-1, left+jump)
		if arr[left] <= x && arr[right] >= x {
			break
		}
		left += jump
	}
	if left >= length || arr[left] > x {
		return -1
	}
	right = min(length-1, right)
	tempIndex := left
	for tempIndex <= right && arr[tempIndex] <= x {
		if arr[tempIndex] == x {
			return tempIndex
		}
		tempIndex++
	}
	return -1
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func resultPrint(element, index int) {
	if index < 0 {
		fmt.Printf("The element %d was not found\n", element)
	} else {
		fmt.Printf("The element %d is at index %d \n", element, index)
	}
}
func main() {
	values := []int{1, 2, 3, 4, 5, 12, 30, 35, 46, 84}
	resultPrint(5, jumpSearch(values, 5))
	resultPrint(7, jumpSearch(values, 7))
}

Tab 5


let array = [0,1,2,5,10,15,20,25,30,33];
let wanted = 2;
pos = jumpSearch(array, wanted);
if(pos == -1) {
    console.log('Value not found');
} else {
    console.log(`Value ${wanted} on position ${pos}`);
}
function jumpSearch(array, wanted) {
    const arrayLength = array.length;
    const block = getValueBlockSearch(arrayLength);
    const foundBlock = findBlockWithWanted(array, arrayLength, wanted, block);
    return findValueInBlock(array, arrayLength, foundBlock, wanted, block);
}
function findBlockWithWanted(array, arrayLength, wanted, block) {
    let step = block;
    let prevStep = 0;
    while(array[getStepPosition(step, arrayLength)] < wanted) {
        prevStep = step;
        step += block;
        if(prevStep >= arrayLength) {
            return -1;
        }
    }
    return prevStep;
}
function findValueInBlock(array, arrayLength, prevStep, wanted, block) {
    if(prevStep == -1) {
        return prevStep;
    }
    while(array[prevStep] </**

Part of Cosmos by OpenGenus Foundation

@param array $array
@param int   $search

@return int

*/

function jumpSearch(array $array, $search)

{

list ($count, $step, $previous) = [$count = count($array), (int) sqrt($count), 0];

while ($array[min($step, $count) - 1] < $search) {

$previous = $step;

$step += (int) sqrt($count);

if ($previous >= $count) {

return -1;

}

}

while ($array[$previous] < $search) {

$previous++;

if ($previous === min($step, $count)) {

return -1;

}

}

return $array[$previous] === $search ? $previous : -1;

}

echo sprintf("Position of %d is %d\n", $search = 33, jumpSearch($array = [7, 11, 13, 33, 66], $search)); wanted) {

prevStep += 1;

if(prevStep == Math.min(block, arrayLength)) {

return -1;

}

}

if(array[prevStep] == wanted) {

return prevStep;

}

return -1;

}

function getStepPosition(step, arrayLength) {

return Math.min(step, arrayLength) - 1;

}

function getValueBlockSearch(length) {

return Math.floor(Math.sqrt(length));

}

Tab 6


/*
 * Part of Cosmos by OpenGenus Foundation
 *
 * @param array $array
 * @param int   $search
 *
 * @return int
 */
function jumpSearch(array $array, $search)
{
    list ($count, $step, $previous) = [$count = count($array), (int) sqrt($count), 0];
    while ($array[min($step, $count) - 1] < $search) {
        $previous = $step;
        $step += (int) sqrt($count);
        if ($previous >= $count) {
            return -1;
        }
    }
    while ($array[$previous] < $search) {
        $previous++;
        if ($previous === min($step, $count)) {
            return -1;
        }
    }
    return $array[$previous] === $search ? $previous : -1;
}
echo sprintf("Position of %d is %d\n", $search = 33, jumpSearch($array = [7, 11, 13, 33, 66], $search));

Tab 7


import math
def jumpSearch(arr, x):
    n = len(arr)
    jump = int(math.sqrt(n))
    left, right = 0, 0
    while left < n and arr[left] >= x:
        right = min(n - 1, left + jump)
        if arr[left] <= x and arr[right] >= x:
            break
        left += jump
    if left >= n or arr[left] > x:
        return -1
    right = min(n - 1, right)
    temp = left
    while temp <= right and arr[temp] <= x:
        if arr[temp] == x:
            return temp
        temp += 1
    return -1
def test(x):
    arr = [7, 18, 24, 12, 47, 84, 14]
    index = jumpSearch(arr, x)
if index != -1:
    print "The element", x, "is at the index", index
else:
    print "Element", x, "not found!"

test(18)

Tab 8


// Part of Cosmos by OpenGenus Foundation
use std::cmp::min;
fn jump_search(arr: Vec<i32>,n :i32) -> i32 {
    let mut step = (arr.len() as f64).sqrt() as usize;
    let len = arr.len();
    let mut prev: usize = 0;
    //Jumps 
    while arr[min(step, len)-1] < n {
        prev = step;
        step += step;
        if prev >= len {
            return -1
        }
    }
    // Linear search
    while arr[prev] < n {
        prev += 1 ;
        if arr[prev] == (min(step, len)) as i32 {
            return -1
        }
    }
    // Element found
    if arr[prev] == n {
        return prev as i32
    }
    -1
}
fn main() {
    let arr = vec![0, 1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 144, 233, 377, 610];
    println!("Found {} at index {}",55,jump_search(arr,55));
}

Tab 9


import Foundation
func jumpSearch<T: Comparable>(_ a: [T], for key: T) -> Int? {
    let count = a.count
    var step = Int(sqrt(Double(count)))
    var previous = 0
    while a[min(step, count) - 1] < key {
        previous = step
        step += Int(sqrt(Double(count)))
        if previous >= count {
            return nil
        }
    }
    while a[previous] < key {
        previous += 1
        if previous == min(step, count) {
            return nil
        }
    }
    return a[previous] == key ? previous : nil
}
if let position = jumpSearch([7, 11, 13, 33, 66], for: 33) {
    print("Found 33 in [7, 11, 13, 33, 66] at position \(position)")
} else {
    print("Can't find 33 in [7, 11, 13, 33, 66]")
}

Applications

If jumping back in a list takes significantly more time than jumping forward then one should use this algorithm.

Can we replace linear search in jump search by binary search?

The use case for jump search (O(√n)) over binary search (O(log n)) is when jumping back is expensive. Replacing the linear search in jump search would be counterproductive in this use case.