A jump search is similar to a linear search; however, it first jumps through the array with a step size (optimally chosen to be √n) and once the appropriate interval is found, call a linear search. The run time is O(√n).

If two levels of jumps are used, the optimal choices for the two jump sizes are n^2/3 and n^1/3 yielding a run time of O(n^1/3). Note that √n^2/3 = n^1/3.

In theory, one could have k jump sizes starting with n^i/k starting with i = k - 1, k - 1, ..., 2, 1, which would have a run time of O(k + n^1/k); however, this is not practical.

The enhanced array- and pointer-based implementations reduce the number of comparisons from three per entry to two. In either case, when the loop ends, the entry at that point is either:

• The last entry of the array, or
• The first entry in the array greater than or equal to the object.

In either case, compare that entry and the object and return the result.