Jump search

Jump search is a searching algorithm to find the position of a searched value in a sorted list by dividing the array into several fixed-size blocks, jumping to the first index of the block, then comparing the value of the block's first index with the searched value. If the value of the block's first index is greater than the searched value, it jumps backward to the previous block, then starts a linear search of the block.

Developing jump search algorithm

Suppose we have an array containing {8, 15, 23, 28, 32, 39, 42, 44, 47, 48} elements, and we want to find the position of value 39. We will set the jump step by the square root elements number. Since the element number of the array is 10, the step will be √10 = 3. We will now compare the value of index 0, 3, 6, and 9. When the algorithm compares array[0] with 39, the value of array[0] is lower than the searched value. It then jumps to array[3] and compares its value with 39. Since the value is lower than the searched value, it...