# Jump Search Algorithm

#### Search Algorithms jump search Algorithms

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.