Jump search (block search) is an algorithm for finding an element in a sorted array in O(√n) time.
Jump search works by iterating over the input array in blocks of size √n and once an element’s value is larger than the target value it converts to a linear search of the current block which must contain the target value.
- The input array is a list of integers sorted from least to greatest.
- The target value is an integer.
Next, we must consider our edge cases.
- If we receive an input array less than 1 element in length we will return -1.
- If the target value is less than the lowest number in our input array we will return -1.
- If the target value is greater than the largest number in our input array we will return -1.
Now we must declare some variables to keep track of our progress in the array and set the block size to jump by. The lower bound will be set to the lowest number in the array and the upper bound set to the largest number in the array.
With our lower and upper bounds declared we will iterate over the array until we come upon a value that is greater than or equal to our target value.
All that's left now is to iterate linearly over the block of the array that contains our target value which is outlined by the lower and upper bounds.
The second for-loop doesn’t increase our time complexity because it doesn’t iterate over the entire dataset, only a single block of size √n.
Here’s the Python version.