관리 메뉴

don't stop believing

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

Golang/Basic

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

Tongchun 2019. 5. 13. 00:17

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

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

 

Jump search - Wikipedia

In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items Lkm, where k ∈ N {\displaystyle k\in \mathbb {N} } and m is the block size, until an item is found that is larger than t

en.wikipedia.org

Go로 구현한 코드입니다.

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)

}

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

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

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

 

0 Comments
댓글쓰기 폼