[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 3. 점프 탐색

1. 선형 탐색 (Linear Search)
2. 이진 탐색 (Binary Search)
3. 점프 탐색 (Jump Search)
4. 보간 탐색 (Interpolation Search)
5. 지수 탐색 (Exponential Search)
6. 깊이 우선 탐색 (Depth-First Search, DFS)
7. 너비 우선 탐색 (Breadth-First Search, BFS)

 

 

점프 탐색

점프 탐색은 정렬된 배열에서 원하는 값을 찾기 위해 고안된 알고리즘으로, 데이터의 특정 구간을 건너뛰며 탐색하여 효율성을 높입니다. 이진 탐색보다 비교 횟수가 적으며, 특히 매우 큰 배열에서 유용하게 사용됩니다.

 

1. 특징

• 구간 탐색: 탐색 과정에서 배열을 작은 블록 단위로 나누고, 일정한 크기로 건너뛰며 목표값을 찾습니다.
• 정렬된 데이터 필요: 점프 탐색은 데이터가 오름차순이나 내림차순으로 정렬된 상태에서 사용할 수 있습니다.
• 균등한 점프 크기: 일반적으로 점프 크기는 √n (데이터의 개수 n의 제곱근)으로 설정하며, 이 값이 최적의 성능을 제공합니다.

 

2. 복잡도

• 시간 복잡도: O(√n). 데이터가 증가할수록 점프 간격이 늘어나며 탐색 시간이 증가하지만, 선형 탐색의 O(n)보다는 빠른 속도를 유지합니다.
• 공간 복잡도: O(1)로, 추가적인 메모리 공간을 거의 사용하지 않습니다.

 

3. 예제

public class JumpSearchExample {
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int step = (int) Math.floor(Math.sqrt(n)); // 점프 크기를 √n으로 설정
        int prev = 0;

        // 점프하면서 범위를 확인
        while (arr[Math.min(step, n) - 1] < target) {
            prev = step;
            step += Math.sqrt(n);
            if (prev >= n) return -1; // 배열 범위 벗어나면 -1 반환
        }

        // 선형 탐색으로 값을 확인
        while (arr[prev] < target) {
            prev++;
            if (prev == Math.min(step, n)) return -1;
        }

        if (arr[prev] == target) return prev; // 값 찾으면 인덱스 반환

        return -1; // 값 없으면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        int result = jumpSearch(arr, target);

        if (result == -1) {
            System.out.println("원소를 찾을 수 없습니다.");
        } else {
            System.out.println("원소는 인덱스 " + result + "에 위치해 있습니다.");
        }
    }
}

• 이 코드는 데이터 배열 arr에서 목표값 target을 찾기 위해 점프 크기(√n)만큼씩 이동하며 범위를 좁힙니다. 목표값이 있을 만한 구간에 도달한 경우, 그 구간에서 선형 탐색을 진행해 값을 찾습니다.

 

4. 주 사용처

• 대규모 정렬 데이터: 데이터가 매우 크고, 완전한 이진 탐색을 하기에는 시간이 많이 걸릴 때 사용됩니다.
• 데이터 검색 및 인덱싱: 빅데이터나 데이터베이스 인덱싱 작업에서 유용합니다.
• 균일한 데이터 분포: 데이터가 균일하게 분포되어 있는 경우 성능이 더욱 향상됩니다.

 

감사합니다.