Jump Search (or Block Search)

Definition

Definition

Jump search, also known as block search, is an algorithm for searching sorted arrays efficiently. It works by jumping ahead by fixed steps to find a range where the target element might be located, then performing a linear search within that range for the exact match

Explanation

Calculate the jump size (or block size) by considering the size of the array and the search key. Then, navigate through the array using this jump size until a range is identified where the search key might be situated. Within this range, conduct a linear search to pinpoint the exact match of the search key. If the key is found, return its index; otherwise, return -1 to signify that the element is not present in the array

Guidance

• Calculate the jump size using the square root of the array size or any other appropriate method
• Start by setting the current position to 0 and the previous position to -1
• Jump ahead by the jump size until the current element is greater than or equal to the search key, or until reaching the end of the array
• Perform a linear search within the range from the previous position to the current position for the search key
• If the search key is found, return its index; otherwise, return -1

Tips

• choose an appropriate jump size to balance between the number of jumps and the number of comparisons
• ensure that the array is sorted before applying the jump search algorithm
• this algorithm works efficiently for large arrays, especially when the cost of random access is high

Practice

Practice

jumpSearch(arr, key):
  n = arr.length
  jump_size = floor(sqrt(n))
  prev = 0
  while n > prev and arr[min(jump_size, n) - 1] < key:
    prev = jump_size
    jump_size += floor(sqrt(n))
    if prev >= n:
      return -1
  for i from prev to min(jump_size, n):
    if arr[i] == key:
      return i
  return -1

Solution

package main

import (
	"math"
)

func jumpSearch(arr []int, x int) int {
	n := len(arr)
	step := int(math.Sqrt(float64(n)))
	prev := 0

	for arr[int(math.Min(float64(step), float64(n))-1)] < x {
		prev = step
		step += int(math.Sqrt(float64(n)))
		if prev >= n {
			return -1
		}
	}

	for arr[prev] < x {
		prev++
		if prev == int(math.Min(float64(step), float64(n))) {
			return -1
		}
	}

	if arr[prev] == x {
		return prev
	}

	return -1
}

import java.lang.Math;

public class JumpSearch {

  public static int jumpSearch(int[] arr, int x) {
    int n = arr.length;
    int step = (int) Math.floor(Math.sqrt(n));
    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;
      }
    }

    while (arr[prev] < x) {
      prev++;
      if (prev == Math.min(step, n)) {
        return -1;
      }
    }

    if (arr[prev] == x) {
      return prev;
    }

    return -1;
  }
}

function jumpSearch(arr, x) {
  const n = arr.length;
  const step = Math.floor(Math.sqrt(n));
  let prev = 0;

  while (arr[Math.min(step, n) - 1] < x) {
    prev = step;
    step += Math.floor(Math.sqrt(n));
    if (prev >= n) {
      return -1;
    }
  }

  while (arr[prev] < x) {
    prev++;
    if (prev === Math.min(step, n)) {
      return -1;
    }
  }

  if (arr[prev] === x) {
    return prev;
  }

  return -1;
}

import kotlin.math.*

fun jumpSearch(arr: IntArray, x: Int): Int {
    val n = arr.size
    val step = sqrt(n.toDouble()).toInt()
    var prev = 0

    while (arr[min(step, n) - 1] < x) {
        prev = step
        step += sqrt(n.toDouble()).toInt()
        if (prev >= n)
            return -1
    }

    while (arr[prev] < x) {
        prev++
        if (prev == min(step, n))
            return -1
    }

    return when {
        arr[prev] == x -> prev
        else -> -1
    }
}

import math

def jump_search(arr, x):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0

    while arr[min(step, n) - 1] < x:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    while arr[prev] < x:
        prev += 1
        if prev == min(step, n):
            return -1

    if arr[prev] == x:
        return prev

    return -1

use std::cmp;

fn jump_search(arr: &[i32], x: i32) -> i32 {
    let n = arr.len();
    let mut step = (n as f64).sqrt() as usize;
    let mut prev = 0;

    while arr[cmp::min(step, n) - 1] < x {
        prev = step;
        step += (n as f64).sqrt() as usize;
        if prev >= n {
            return -1;
        }
    }

    while arr[prev] < x {
        prev += 1;
        if prev == cmp::min(step, n) {
            return -1;
        }
    }

    if arr[prev] == x {
        return prev as i32;
    }

    -1
}

function jumpSearch(arr: number[], x: number): number {
  const n: number = arr.length;
  const step: number = Math.floor(Math.sqrt(n));
  let prev: number = 0;

  while (arr[Math.min(step, n) - 1] < x) {
    prev = step;
    step += Math.floor(Math.sqrt(n));
    if (prev >= n) return -1;
  }

  while (arr[prev] < x) {
    prev++;
    if (prev === Math.min(step, n)) return -1;
  }

  if (arr[prev] === x) return prev;

  return -1;
}