# Jump Search Algorithm

#### Search Algorithms jump search Algorithms Get FREE domain for 1st year and build your brand new site

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.

** 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)
{
}
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))
if (curr != begin)
// 2. Doing a linear search for find in block
while (curr < end && sqrtDist-- > 0 && comp(*curr, find))
// 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;
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 {
}
}

``````}
``````

### 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 {
} 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) {
} 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:

``````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. #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.

Improved & Reviewed by: