[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 5. 지수 탐색

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. 특징

• 이진 탐색을 기반으로 한 빠른 탐색: 지수적으로 증가하는 간격으로 탐색 범위를 늘려나가며 찾고자 하는 값의 위치 범위를 빠르게 좁힙니다.
• 정렬된 배열에서만 사용 가능: 배열이 정렬되어 있어야 하며, 그렇지 않은 경우에는 오작동할 수 있습니다.
• 범위 내 검색: 탐색할 값이 있는 범위만 설정하여 이진 탐색을 수행하므로, 값이 존재하지 않으면 탐색이 빠르게 종료됩니다.

 

2. 복잡도

• 시간 복잡도: 최악의 경우 O(log⁡n)O(\log n)O(logn)로, 정렬된 배열에서 이진 탐색과 같은 효율을 보입니다.
• 공간 복잡도: O(1)로, 추가 메모리 사용이 거의 없기 때문에 메모리 효율이 높습니다.

 

3. 예제

import java.util.Arrays;

public class ExponentialSearchExample {
    public static int exponentialSearch(int[] arr, int target) {
        int n = arr.length;

        // 첫 번째 요소가 target인 경우 즉시 반환
        if (arr[0] == target)
            return 0;

        // 지수적으로 증가하며 범위 찾기
        int i = 1;
        while (i < n && arr[i] <= target)
            i *= 2;

        // 이진 탐색 수행 (범위 내에서만)
        return Arrays.binarySearch(arr, i / 2, Math.min(i, n), target);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
        int target = 64;
        int result = exponentialSearch(arr, target);

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

• 이 코드는 배열 arr에서 target 값을 찾아 반환합니다. 먼저 작은 범위로 시작해 지수적으로 범위를 확장하며 값을 찾고, 예상 범위를 이진 탐색으로 좁히는 방식으로 동작합니다.

 

4. 주 사용처

• 정렬된 데이터의 신속한 탐색: 데이터가 정렬되어 있지만 크기를 알 수 없는 경우 유용합니다.
• 범위가 큰 데이터 탐색: 크기가 크고 정렬된 배열에서 데이터 범위를 빠르게 좁혀 탐색할 때 사용됩니다.
• 데이터 분석 및 검색 시스템: 대규모 데이터셋에서 특정 값을 신속하게 검색할 수 있는 알고리즘으로 사용됩니다.

 

감사합니다.