[기초] C++ 점프 탐색 (Jump Search)

---

 

점프 탐색(Jump Search)은 정렬된 배열에서 원하는 값을 찾기 위해 사용되는 알고리즘입니다.

이 알고리즘은 배열의 요소를 하나씩 검사하지 않고,

일정한 "블록" 단위로 건너뛰며 검사하여 효율적으로 탐색합니다.

점프 탐색의 시간 복잡도는 O(√n)이며,

이 알고리즘은 이진 탐색(Binary Search)과 비슷한 상황에서 유용하게 사용될 수 있습니다.

 

---

 

동작 원리

 

• 배열의 크기를 n이라고 할 때, √n 크기의 블록으로 나눕니다.
  
  
• 현재 블록의 마지막 요소가 탐색하려는 값보다 작으면 다음 블록으로 이동합니다.
  
  
• 현재 블록의 마지막 요소가 탐색하려는 값보다 크거나 같으면 해당 블록 내에서 선형 탐색을 수행합니다.
  
  

#include <iostream>
#include <cmath>

int jumpSearch(int arr[], int n, int x) {
    // 초기 블록 크기 설정
    int step = sqrt(n);
    int prev = 0;

    // x가 속한 블록을 찾기
    while (arr[std::min(step, n) - 1] < x) {
        prev = step;
        step += sqrt(n);
        if (prev >= n) {
            return -1; // 배열의 끝에 도달하면 -1 반환
        }
    }

    // 해당 블록 내에서 선형 탐색 수행
    for (int i = prev; i < std::min(step, n); i++) {
        if (arr[i] == x) {
            return i; // 찾으면 인덱스 반환
        }
    }

    return -1; // 찾지 못하면 -1 반환
}

int main() {
    int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 55;

    int index = jumpSearch(arr, n, x);

    if (index != -1) {
        std::cout << "Element " << x << " is at index " << index << std::endl;
    } else {
        std::cout << "Element " << x << " not found in the array" << std::endl;
    }

    return 0;
}

 

출력

 

Element 55 is at index 10

 

 

이 예제에서는 'arr' 배열에서 '55'를 찾는 과정을 보여줍니다.

점프 탐색 알고리즘은 배열을 블록 단위로 탐색하여 효율적으로 값을 찾습니다.

블록 크기는 'sqrt(n)'로 설정되며,

'55'를 찾기 위해 각 블록의 마지막 요소를 검사하면서 적절한 블록을 찾습니다.

그 후, 해당 블록 내에서 선형 탐색을 수행하여 '55'의 위치를 반환합니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀