jump.jule

// description: Implementation of jump search
// details:
// A search algorithm for ordered list that jump through the list to narrow down the range
// before performing a linear search
// reference: https://en.wikipedia.org/wiki/Jump_search
// see jump_test.go for a test implementation, test function TestJump

use "std/math"

// Search works by jumping multiple steps ahead in sorted list until it find an item larger than target,
// then create a sublist of item from the last searched item up to the current item and perform a linear search.
fn Jump(array: []int, target: int)!: int {
	n := len(array)
	if n == 0 {
		error(Error.NotFound)
	}

	// the optimal value of step is square root of the length of list
	step := int(math::Round(math::Sqrt(f64(n))))

	mut prev := 0    // previous index
	mut curr := step // current index
	for array[curr-1] < target {
		prev = curr
		if prev >= len(array) {
			error(Error.NotFound)
		}

		curr += step

		// prevent jumping over list range
		if curr > n {
			curr = n
		}
	}

	// perform linear search from index prev to index curr
	for array[prev] < target {
		prev++

		// if reach end of range, indicate target not found
		if prev == curr {
			error(Error.NotFound)
		}
	}
	if array[prev] == target {
		ret prev
	}

	error(Error.NotFound)
}