jump search Algorithm
Jump search is an efficient searching algorithm that is particularly useful when applied to an ordered list of elements. It works by dividing the list into smaller sublists, or blocks, and then jumping between these blocks to determine the range within which the desired element may be located. The algorithm uses an optimal block size (usually determined by the square root of the list's length) to maximize the search efficiency. Once the appropriate block is identified, a linear search is performed within the block to find the desired element. This hybrid approach of combining a jump search with a linear search allows for faster search times compared to a linear search alone, while maintaining simplicity and ease of implementation.
The jump search algorithm begins by comparing the desired element with the first element of every block in the list. If the element is found to be less than or equal to the last element of a block, the search is narrowed down to that specific block. If the element is greater than the last element of a block, the algorithm jumps to the next block and repeats the process. If the element is not found in any of the blocks, it can be concluded that the element is not present in the list. Once the correct block is identified, a linear search is performed within that block to locate the exact position of the desired element. This combination of jumping between blocks and linear search within a block ensures that the jump search algorithm performs fewer iterations than a linear search, resulting in faster search times overall.
import math
def jump_search(arr, x):
n = len(arr)
step = int(math.floor(math.sqrt(n)))
prev = 0
while arr[min(step, n) - 1] < x:
prev = step
step += int(math.floor(math.sqrt(n)))
if prev >= n:
return -1
while arr[prev] < x:
prev = prev + 1
if prev == min(step, n):
return -1
if arr[prev] == x:
return prev
return -1
if __name__ == "__main__":
arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
x = 55
print(f"Number {x} is at index {jump_search(arr, x)}")
