Jump Point Search - 점프 포인트 서치 (블록 탐색)

선형 검색(Linear Search)의 경우 배열의 첫번째 자리에서부터 값을 찾아 값니다. 
하지만 찾으려는 값이 뒷쪽에 있다면 효율이 좋지 않기 때문에 하나씩 올라가지 않고 일정 블록을 잡아서 점프해 가며 찾겠습니다.

https://en.wikipedia.org/wiki/Jump_search

Jump search - Wikipedia

Go로 구현한 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package main
import "fmt"
import "math"
func jumpSearch(arr []int, key int) int {
    // 점프할 블록을 계산합니다. math.Sqrt를 사용했습니다. (재곱근: square root)
    sz := len(arr)
    step := int(math.Sqrt(float64(sz)))
    prev := 0
    // 배열에서 점프한 블록의 값이 찾으려는 값보다 작다면 loop를 계속 진행합니다.
    // 찾으려는 값보다 큰 수가 있을 경우 prev 변수에 블럭 자리를 저장합니다. 만약 배열이 끝날때까지 찾지 못했다면 -1을 리턴합니다.
    for arr[int(math.Min(float64(step), float64(sz)))-1] < key {
        prev = step
        step += int(math.Sqrt(float64(sz)))
        if prev >= sz {
            return -1
        }
    }
    // 찾으려는 값이 prev 변수에 입력된 자릿수보다 큰 것입니다.
    // 자릿수를 하나찍 올려 선형 검색을 해가면 찾습니다.
    for arr[prev] < key {
        prev++
        if prev == int(math.Min(float64(step), float64(sz))) {
            return -1
        }
    }
    // 찾으려는 값의 자릿수를 찾았다면 자릿수를 리턴합니다.
    if arr[prev] == key {
        return prev
    }
    return -1
}
func main() {
    // 우선 전제조건으로 검색하려는 배열은 정렬되어 있어야 합니다.
    arr := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
    key := 55
    index := jumpSearch(arr, key)
    fmt.Println(index)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

점프할 블록을 잡을때 아래와 같이 전체 배열의 길이에 대한 재곱근으로 잡았습니다.

int(math.Sqrt(float64(len(arr))))

블록 단위로 점프하며 찾으려는 값보다 큰지를 비교하게됩니다.
찾으려는 값이 뒤에 있다면 0번째 자리부터 하나씩 찾는 것보다는 효율이 좋습니다.