점프 탐색(Jump search) 개념 및 구현
Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다.
정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다.
이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다.
동작 방식
- 배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다.
- m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다.
- m = √n
- 한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다.
- 값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다.
블록 최적 사이즈 구하는 과정
m에 최적 값을 구하는 공식은 다음과 같습니다.
블록 크기가 m이고 n개의 요소를 가지고 있다면 점프 탐색에서 총 n/m 번 블록을 탐색하게 됩니다.
이후 선형 탐색은 m -1 만큼 일어나기 때문에 총 n/m + m - 1 만큼 수행하게 됩니다.
이 상황에서 m에 최적해는 다음 공식으로 구할 수 있습니다.
\( \frac{d}{dm}(n/m + m - 1) = 0 \)
\( -nm^{-2} + 1 = 0 \)
\( nm^{-2} = 1 \)
\(m = \sqrt{n} \)
m이 √n 일 때 수행을 최소화할 수 있습니다.
검색 예
다음은 배열 arr[11] ={1,2,3,4,5,6,7,8,9,10,11} 에서 key=8을 찾는 예입니다.
1. 블록 사이즈 m을 구합니다.
- m=√11 = 3
2. key 값을 포함한 블록을 찾을 때까지 탐색을 합니다.
- 첫 번째 블록을 확인합니다. 블록의 최댓값이 x값보다 작기 때문에 다음 블록으로 이동합니다. (arr[2] < key)
- 두 번째 블록을 확인합니다. 블록의 최댓값이 key값보다 작기 때문에 다음 블록으로 이동합니다. (arr[5] < key)
- 세 번째 블록을 확인합니다. 블록이 key값을 포함하고 있습니다.
3. 세번째 블록 첫 번째 인덱스부터 선형 탐색으로 key값을 찾습니다.
종료 조건
점프 탐색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 탐색을 종료합니다.
1. 검색을 성공할 경우
- 검색키를 가진 블록을 발견한 경우
2. 검색을 실패한 경우
- 더 이상 검색할 블록이 없는 경우
구현
위 종료 조건을 가지고 구현을 하면 다음과 같습니다.
이 함수는 검색을 성공하면 요소의 인덱스를 리턴하고 실패하면 -1을 리턴합니다.
int jumpSearch(int arr[], int n, int key)
{
// 점프하기 위한 블록 크기 m을 구함.
int m = sqrt(n);
int prev = 0;
// 블록 크기 만큼 점프하면서 key값을 포함하는 블록을 찾음
while (arr[min(m, n)-1] < key)
{
prev = m;
m += m; // 블록 크기 만큼 점프.
if (prev >= n) // 배열 인덱스를 초과하는 경우, 검색 실패
return -1;
}
// key값을 포함한 블록을 찾았다면
// 블록의 첫번째 인덱스부터 선형 탐색 시작
while (arr[prev] < key)
{
prev++;
if (prev == min(m, n)) // 블록 범위를 초과하는 경우, 검색 실패
return -1;
}
// 검색 값을 찾은 경우
if (arr[prev] == key)
return prev;
return -1;
}
시간 복잡도(Time complexity)
n은 요소 수, m은 블록 크기라고 했을 때, 점프 탐색의 총 수행 횟수는 n/m + m -1이고 m에 최적 값은 √n 이기 때문에 시간 복잡도는 다음과 같습니다.
시간 복잡도 = n/m + m - 1
= n/√n + √n - 1
= 2√n -1
= O(√n)
| Operation | Best | Average | Worst |
| Search | O(1) | Θ(√n) | O(√n) |
*n = 데이터 수
