Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Add Jump Search algorithm in Java#6407

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
Fahham2903 wants to merge11 commits intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromFahham2903:add-jump-search
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
Show all changes
11 commits
Select commitHold shift + click to select a range
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
68 changes: 28 additions & 40 deletionssrc/main/java/com/thealgorithms/searches/JumpSearch.java
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,56 +1,44 @@
package com.thealgorithms.searches;

import com.thealgorithms.devutils.searches.SearchAlgorithm;

/**
* An implementation of the Jump Search algorithm.
*
* <p>
* Jump Search is an algorithm for searching sorted arrays. It works by dividing the array
* into blocks of a fixed size (the block size is typically the square root of the array length)
* and jumping ahead by this block size to find a range where the target element may be located.
* Once the range is found, a linear search is performed within that block.
*
* <p>
* The Jump Search algorithm is particularly effective for large sorted arrays where the cost of
* performing a linear search on the entire array would be prohibitive.
* Implementation of Jump Search algorithm.
*
* <p>
* Worst-case performance: O(√N)<br>
* Best-case performance: O(1)<br>
* Average performance: O(√N)<br>
* Worst-case space complexity: O(1)
* Time Complexity: O(√n)
* Space Complexity: O(1)
*
* <p>
* This class implements the {@link SearchAlgorithm} interface, providing a generic search method
* for any comparable type.
* Reference: https://en.wikipedia.org/wiki/Jump_search
*/
public class JumpSearch implements SearchAlgorithm {
public final class JumpSearch {

// Prevent instantiation
private JumpSearch() {
throw new UnsupportedOperationException("Utility class");
}

/**
* Jump Search algorithm implementation.
*
* @param array the sorted array containing elements
* @param key the element to be searched
* @return the index of {@code key} if found, otherwise -1
*/
@Override
public <T extends Comparable<T>> int find(T[] array, T key) {
int length = array.length;
int blockSize = (int) Math.sqrt(length);
public static int jumpSearch(int[] arr, int target) {
int n = arr.length;
int step = (int) Math.floor(Math.sqrt(n));
int prev = 0;

int limit = blockSize;
// Jumping ahead to find the block where the key may be located
while (limit < length && key.compareTo(array[limit]) > 0) {
limit = Math.min(limit + blockSize, length - 1);
while (prev < n && arr[Math.min(step, n) - 1] < target) {
prev = step;
step += (int) Math.floor(Math.sqrt(n));
}

// Perform linear search within the identified block
for (int i = limit - blockSize; i <= limit && i < length; i++) {
if (array[i].equals(key)) {
for (int i = prev; i < Math.min(step, n); i++) {
if (arr[i] == target) {
return i;
}
}

return -1;
}

public static int find(Integer[] arr, Integer target) {
int[] array = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
array[i] = arr[i];
}
return jumpSearch(array, target);
}
}
65 changes: 17 additions & 48 deletionssrc/test/java/com/thealgorithms/searches/JumpSearchTest.java
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -4,91 +4,60 @@

import org.junit.jupiter.api.Test;

/**
* Unit tests for the JumpSearch class.
*/
class JumpSearchTest {

/**
* Test for finding an element present in the array.
*/
@Test
void testJumpSearchFound() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Integer key = 5; // Element to find
assertEquals(5,jumpSearch.find(array, key), "The index of the found element should be 5.");
Integer key = 5;
assertEquals(5,JumpSearch.find(array, key));
}

/**
* Test for finding the first element in the array.
*/
@Test
void testJumpSearchFirstElement() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Integer key = 0; // First element
assertEquals(0,jumpSearch.find(array, key), "The index of the first element should be 0.");
Integer key = 0;
assertEquals(0,JumpSearch.find(array, key));
}

/**
* Test for finding the last element in the array.
*/
@Test
void testJumpSearchLastElement() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Integer key = 10; // Last element
assertEquals(10,jumpSearch.find(array, key), "The index of the last element should be 10.");
Integer key = 10;
assertEquals(10,JumpSearch.find(array, key));
}

/**
* Test for finding an element not present in the array.
*/
@Test
void testJumpSearchNotFound() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Integer key = -1; // Element not in the array
assertEquals(-1,jumpSearch.find(array, key), "The element should not be found in the array.");
Integer key = -1;
assertEquals(-1,JumpSearch.find(array, key));
}

/**
* Test for finding an element in an empty array.
*/
@Test
void testJumpSearchEmptyArray() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {}; // Empty array
Integer key = 1; // Key not present
assertEquals(-1, jumpSearch.find(array, key), "The element should not be found in an empty array.");
Integer[] array = {};
Integer key = 1;
assertEquals(-1, JumpSearch.find(array, key));
}

/**
* Test for finding an element in a large array.
*/
@Test
void testJumpSearchLargeArray() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = new Integer[1000];
for (int i = 0; i < array.length; i++) {
array[i] = i * 2; // Fill the array with even numbers
array[i] = i * 2;
}
Integer key = 256; // Present in the array
assertEquals(128,jumpSearch.find(array, key), "The index of the found element should be 128.");
Integer key = 256;
assertEquals(128,JumpSearch.find(array, key));
}

/**
* Test for finding an element in a large array when it is not present.
*/
@Test
void testJumpSearchLargeArrayNotFound() {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = new Integer[1000];
for (int i = 0; i < array.length; i++) {
array[i] = i * 2; // Fill the array with even numbers
array[i] = i * 2;
}
Integer key = 999; // Key not present
assertEquals(-1,jumpSearch.find(array, key), "The element should not be found in the array.");
Integer key = 999;
assertEquals(-1,JumpSearch.find(array, key));
}
}
Loading
[8]ページ先頭
©2009-2025 Movatter.jp