점프 검색(Jump Search)은 정렬된 리스트에서 사용할 수 있는 탐색 기법입니다. 이 방법은 데이터를 일정 크기의 블록으로 나누고, 각 블록 안에서 찾고자 하는 요소가 있는지 확인하는 방식으로 동작합니다. 만약 해당 블록에 찾는 값이 없다면 전체 블록을 다음 구간으로 건너뛰어 이동합니다.
블록의 크기는 리스트의 전체 크기를 기준으로 정해집니다. 리스트의 크기가 n이라면 블록 크기는 √n이 됩니다. 올바른 블록을 찾은 후에는 그 블록 내부에서 선형 검색(Linear Search)을 수행하여 실제 값을 찾아냅니다.
점프 검색의 성능은 선형 검색과 이진 검색(Binary Search) 사이에 위치한다는 특징이 있습니다. 이진 검색보다는 느리지만, 선형 검색보다는 훨씬 빠르게 동작하며, 되돌아가는 이동(backward jump)이 적어 특정 상황에서 유용하게 활용됩니다.
점프 검색의 복잡도
- 시간 복잡도: O(√n)
- 공간 복잡도: O(1)
입력 및 출력 예시
입력: 정렬된 데이터 목록: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 검색 키: 356 출력: Item found at location: 11
알고리즘 의사코드
jumpSearch(array, size, key)
입력: 정렬된 배열, 배열의 크기, 검색할 키 값
출력: 키를 찾은 경우 해당 위치(index), 찾지 못한 경우 유효하지 않은 위치(-1)
Begin
blockSize := √size
start := 0
end := blockSize
while array[end] <= key AND end < size do
start := end
end := end + blockSize
if end > size – 1 then
end := size
done
for i := start to end -1 do
if array[i] = key then
return i
done
return invalid location
EndC++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
int jumpSearch(int array[], int size, int key) {
int start = 0;
int end = sqrt(size); // 배열 길이의 제곱근
while(array[end] <= key && end < size) {
start = end; // 올바른 블록이 아니면 블록을 이동
end += sqrt(size);
if(end > size - 1)
end = size; // 범위를 초과하면 경계로 제한
}
for(int i = start; i<end; i++) { // 선택된 블록 내에서 선형 검색 수행
if(array[i] == key)
return i; // 키의 정확한 위치 반환
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n]; // 크기 n의 배열 생성
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = jumpSearch(arr, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}실행 결과
Enter number of items: 20 Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Enter search key to search in the list: 356 Item found at location: 11
마무리
점프 검색은 정렬된 데이터에서 √n 단위로 건너뛰며 탐색 범위를 좁혀 나간 뒤, 마지막에는 선형 검색으로 정확한 위치를 찾는 효율적인 알고리즘입니다. 시간 복잡도 O(√n)과 공간 복잡도 O(1)이라는 특성 덕분에 메모리 사용이 적으면서도 선형 검색 대비 우수한 성능을 제공합니다.