Jump Search is a search algorithm designed for sorted datasets. It works by dividing the dataset into fixed-size blocks and “jumping” ahead by that block size until the target value is within the range of a block. Once located, it performs a linear search within that block to find the exact position of the target element.
How Jump Search Works?
- Calculate Jump Size:
The jump size is usually sqrt(n), where n is the size of the dataset. - Jump Through Blocks:
Start at the beginning and jump ahead by the block size until the target value is smaller than the current value or the end of the array is reached. - Linear Search:
Perform a linear search within the identified block to locate the exact position of the target element. - Return Result:
If the target is found, return its index; otherwise, return-1.
Jump Search Java Program Examples
In this article, we’ll explore Jump Search with two Java programs: a basic example for numeric arrays and an advanced implementation for searching within custom object lists.
1. Basic Program Example
This basic Java program implements Jump Search on a sorted array of integers to efficiently locate the target value using block jumps and linear search.
package com.javacodepoint.search;
public class BasicJumpSearch {
public static int jumpSearch(int[] array, int key) {
int n = array.length;
int step = (int) Math.sqrt(n);
int prev = 0;
// Jump through blocks
while (array[Math.min(step, n) - 1] < key) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n) {
return -1;
}
}
// Linear search within the block
while (array[prev] < key) {
prev++;
if (prev == Math.min(step, n)) {
return -1;
}
}
// Check if the key is found
if (array[prev] == key) {
return prev;
}
return -1;
}
public static void main(String[] args) {
int[] numbers = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
int key = 50;
int result = jumpSearch(numbers, key);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found.");
}
}
}
OUTPUT:
Element found at index: 4
2. Advanced Program Example
This advanced program example uses Jump Search to locate a Product in a sorted list by its price. It highlights the algorithm’s ability to handle complex data structures efficiently.
package com.javacodepoint.search;
import java.util.ArrayList;
import java.util.List;
class Product {
private int price;
private String name;
public Product(int price, String name) {
this.price = price;
this.name = name;
}
public int getPrice() {
return price;
}
@Override
public String toString() {
return "Product{name='" + name + "', price=" + price + "}";
}
}
public class AdvancedJumpSearch {
public static int jumpSearch(List<Product> products, int key) {
int n = products.size();
int step = (int) Math.sqrt(n);
int prev = 0;
// Jump through blocks
while (products.get(Math.min(step, n) - 1).getPrice() < key) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n) {
return -1;
}
}
// Linear search within the block
while (products.get(prev).getPrice() < key) {
prev++;
if (prev == Math.min(step, n)) {
return -1;
}
}
// Check if the key is found
if (products.get(prev).getPrice() == key) {
return prev;
}
return -1;
}
public static void main(String[] args) {
List<Product> products = new ArrayList<>();
products.add(new Product(100, "Laptop"));
products.add(new Product(200, "Tablet"));
products.add(new Product(300, "Smartphone"));
products.add(new Product(400, "Smartwatch"));
int key = 300;
int result = jumpSearch(products, key);
if (result != -1) {
System.out.println("Product found: " + products.get(result));
} else {
System.out.println("Product not found.");
}
}
}
OUTPUT:
Product found: Product{name=’Smartphone’, price=300}
Jump Search Efficiency
You can explore other search algorithms like Linear Search, Binary Search, Interpolation Search, Fibonacci Search, Exponential Search, and Ternary Search.