Jump 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.
(array []int, target int)
| 15 | // Jump search works by jumping multiple steps ahead in sorted list until it find an item larger than target, |
| 16 | // then create a sublist of item from the last searched item up to the current item and perform a linear search. |
| 17 | func Jump(array []int, target int) (int, error) { |
| 18 | n := len(array) |
| 19 | if n == 0 { |
| 20 | return -1, ErrNotFound |
| 21 | } |
| 22 | |
| 23 | // the optimal value of step is square root of the length of list |
| 24 | step := int(math.Round(math.Sqrt(float64(n)))) |
| 25 | |
| 26 | prev := 0 // previous index |
| 27 | curr := step // current index |
| 28 | for array[curr-1] < target { |
| 29 | prev = curr |
| 30 | if prev >= len(array) { |
| 31 | return -1, ErrNotFound |
| 32 | } |
| 33 | |
| 34 | curr += step |
| 35 | |
| 36 | // prevent jumping over list range |
| 37 | if curr > n { |
| 38 | curr = n |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | // perform linear search from index prev to index curr |
| 43 | for array[prev] < target { |
| 44 | prev++ |
| 45 | |
| 46 | // if reach end of range, indicate target not found |
| 47 | if prev == curr { |
| 48 | return -1, ErrNotFound |
| 49 | } |
| 50 | } |
| 51 | if array[prev] == target { |
| 52 | return prev, nil |
| 53 | } |
| 54 | |
| 55 | return -1, ErrNotFound |
| 56 | |
| 57 | } |
no outgoing calls