A jump search locates an item in a sorted array by jumping k itens and then verify if the item wanted is between the previous jump and current jump.

Complexity Worst Case

O(√N)

How it works

  1. Define the value of k, the number of jump: Optimal jump size is √N where the N is the length of array
  2. Jump the array k-by-k searching by the condition Array[i] < valueWanted < Array[i+k]
  3. Do a linear search between Array[i] and Array[i + k]
Jumping Search 1

Code

To view examples of code implementation of this method access this link below:

Jump Search - OpenGenus/cosmos

Credits

The logic’s array image