Jump Search Algorithm Code Implementations
Complete Jump Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Jump Search Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Jump Search Implementation in C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
class JumpSearch {
public:
static int jumpSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return -1;
// Finding the optimal jump size
int jumpSize = static_cast<int>(sqrt(n));
int step = jumpSize;
int prev = 0;
// Finding the block where element is present
while (step < n && arr[std::min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
// Linear search in the identified block
while (prev < std::min(step, n)) {
if (arr[prev] == target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search with custom jump size
static int jumpSearchCustom(const std::vector<int>& arr, int target, int jumpSize) {
int n = arr.size();
if (n == 0) return -1;
int step = jumpSize;
int prev = 0;
while (step < n && arr[std::min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < std::min(step, n)) {
if (arr[prev] == target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search for finding insertion point
static int jumpSearchInsertion(const std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return 0;
int jumpSize = static_cast<int>(sqrt(n));
int step = jumpSize;
int prev = 0;
while (step < n && arr[std::min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < std::min(step, n)) {
if (arr[prev] >= target) {
return prev;
}
prev++;
}
return prev;
}
};JAVA Implementation
// Jump Search Implementation in Java
import java.lang.Math;
public class JumpSearch {
public static int jumpSearch(int[] arr, int target) {
int n = arr.length;
if (n == 0) return -1;
// Finding the optimal jump size
int jumpSize = (int) Math.sqrt(n);
int step = jumpSize;
int prev = 0;
// Finding the block where element is present
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
// Linear search in the identified block
while (prev < Math.min(step, n)) {
if (arr[prev] == target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search with custom jump size
public static int jumpSearchCustom(int[] arr, int target, int jumpSize) {
int n = arr.length;
if (n == 0) return -1;
int step = jumpSize;
int prev = 0;
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < Math.min(step, n)) {
if (arr[prev] == target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search for finding insertion point
public static int jumpSearchInsertion(int[] arr, int target) {
int n = arr.length;
if (n == 0) return 0;
int jumpSize = (int) Math.sqrt(n);
int step = jumpSize;
int prev = 0;
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < Math.min(step, n)) {
if (arr[prev] >= target) {
return prev;
}
prev++;
}
return prev;
}
}JAVASCRIPT Implementation
// Jump Search Implementation in JavaScript
function jumpSearch(arr, target) {
const n = arr.length;
if (n === 0) return -1;
// Finding the optimal jump size
const jumpSize = Math.floor(Math.sqrt(n));
let step = jumpSize;
let prev = 0;
// Finding the block where element is present
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
// Linear search in the identified block
while (prev < Math.min(step, n)) {
if (arr[prev] === target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search with custom jump size
function jumpSearchCustom(arr, target, jumpSize) {
const n = arr.length;
if (n === 0) return -1;
let step = jumpSize;
let prev = 0;
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < Math.min(step, n)) {
if (arr[prev] === target) {
return prev;
}
prev++;
}
return -1;
}
// Jump Search for finding insertion point
function jumpSearchInsertion(arr, target) {
const n = arr.length;
if (n === 0) return 0;
const jumpSize = Math.floor(Math.sqrt(n));
let step = jumpSize;
let prev = 0;
while (step < n && arr[Math.min(step, n - 1)] < target) {
prev = step;
step += jumpSize;
}
while (prev < Math.min(step, n)) {
if (arr[prev] >= target) {
return prev;
}
prev++;
}
return prev;
}PYTHON Implementation
# Jump Search Implementation in Python
import math
def jump_search(arr, target):
n = len(arr)
if n == 0:
return -1
# Finding the optimal jump size
jump_size = int(math.sqrt(n))
step = jump_size
prev = 0
# Finding the block where element is present
while step < n and arr[min(step, n - 1)] < target:
prev = step
step += jump_size
# Linear search in the identified block
while prev < min(step, n):
if arr[prev] == target:
return prev
prev += 1
return -1
# Jump Search with custom jump size
def jump_search_custom(arr, target, jump_size):
n = len(arr)
if n == 0:
return -1
step = jump_size
prev = 0
while step < n and arr[min(step, n - 1)] < target:
prev = step
step += jump_size
while prev < min(step, n):
if arr[prev] == target:
return prev
prev += 1
return -1
# Jump Search for finding insertion point
def jump_search_insertion(arr, target):
n = len(arr)
if n == 0:
return 0
jump_size = int(math.sqrt(n))
step = jump_size
prev = 0
while step < n and arr[min(step, n - 1)] < target:
prev = step
step += jump_size
while prev < min(step, n):
if arr[prev] >= target:
return prev
prev += 1
return prev