﻿ Java - Find an element in a sorted array using Jump Search

# Java: Find a specified element in a given sorted array of elements using Jump Search

## Java Search: Exercise-3 with Solution

Write a Java program to find a specified element in a given sorted array of elements using Jump Search.

From Wikipedia, in computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items Lkm, where ℜ ∈ ℵ and m is the block size, until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is performed on the sublist L[(k-1)m, km].
Algorithm:
Input: An ordered list L, its length n and a search key s.
Output: The position of s in L, or nothing if s is not in L.

```  a ← 0
b ← [√n]

while Lmin(b,n)-1 < s do
a ← b
b ← b + [√n]
if a ≥ n then
return nothing

while La < s do
a ← a + 1
if a = min(b,n)
return nothing

if La = s then
return a
else
return nothing
```

Sample Solution:

Java Code:

``````public class Main {

public static void main(String[] args) {
int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 21, 34, 45, 91, 120, 130, 456, 564};
int search_num = 120;

// Find the index of searched item
int index_result = jumpSearch(nums, search_num);

System.out.println(search_num + " is found at index " + index_result);

}

public static int jumpSearch(int[] nums, int item)	    {

int array_size = nums.length;

// Find block size to be jumped
int block_size = (int)Math.floor(Math.sqrt(array_size));

// If the element is present find the block where element is present
int prev_item = 0;
while (nums[Math.min(block_size, array_size)-1] < item)
{
prev_item = block_size;
block_size += (int)Math.floor(Math.sqrt(array_size));
if (prev_item >= array_size)
return -1;
}

// Using a linear search for element in block beginning with previous item
while (nums[prev_item] < item)
{
prev_item++;
if (prev_item == Math.min(block_size, array_size))
return -1;
}

// If element is found
if (nums[prev_item] == item)
return prev_item;

return -1;
}
}
```
```

Sample Output:

```120 is found at index 12
```

Flowchart:

Java Code Editor: