Jump search

Another search algorithm that can improve performance with sorted arrays is the jump search. A jump search bears some similarity to both the linear search and binary search algorithms in that it searches blocks of elements from left to right beginning with the first block in the collection, and also because at each jump the algorithm compares the search key value to the value of the element at the current step. If the algorithm determines that the key could exist in the current subset of elements, the next step (no pun intended) is to examine each element in the current subset to determine if it is less than the key.

Once an element is found that is not less than the key , that element is compared to the key. If the element is equal to the key, it is returned; otherwise, it is greater than the key, which means that the key does not exist in the collection.

The jump length m is not an arbitrary value, but rather is calculated based on the length of the collection using the...