AntInLoop

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