Jump Search
A jump search locates an item in a sorted array by jumping k items in the array and then verifies if the item wanted is between the previous jump and current jump.
Worst Case Complexity
O(√N)
How does it work ?
- Define the value of k, the number of jumps: The optimal jump size is √N where N is the length of the sorted array.
- Jump over the array elements by k everytime, checking the following condition
Array[i] < valueWanted < Array[i+k]
. - If the previous condition is true, then do a linear search between
Array[i]
andArray[i + k]
. - Return the position of the value if it is found in the array.

Code In Java.
public int jumpSearch(int[] arr, int x)
{
int n = arr.length;
// Finding the size to be jumped
int jumpSize = (int) Math.floor(Math.sqrt(n));
// Finding the index where element is present
int index = 0;
while (arr[Math.min(jumpSize, n)-1] < x)
{
index = jumpSize;
jumpSize += (int) Math.floor(Math.sqrt(n));
if (index >= n)
return -1;
}
// Searching for x beginning with index.
while (arr[index] < x)
{
index++;
// If we reached next index or end of array then element is not present.
if (index == Math.min(jumpSize, n))
return -1;
}
// If element is found
if (arr[index] == x)
return index;
return -1;
}
Code
To view examples of code implementation for this method, access this link below:
Jump Search – OpenGenus/cosmos