[기초] C++ 지수 탐색 (Exponential Search)

---

 

지수 탐색(Exponential Search)은 정렬된 배열에서 효율적으로 원하는 값을 찾기 위한 알고리즘 중 하나입니다.

지수 탐색은 이진 탐색(Binary Search)을 확장한 것으로,

먼저 지수를 사용해 검색 범위를 좁히고,

이후 이진 탐색을 사용해 값을 찾습니다.

이 방법은 O(log n) 시간 복잡도를 가지며,

특히 요소가 배열의 앞쪽에 있을 때 더 빠르게 찾을 수 있습니다.

 

---

동작 원리

 

• 지수 범위 설정
  검색하려는 값이 배열에 존재하는 범위를 지수적으로 확장하여 찾습니다.
  
  
• 이진 탐색 적용
  지수로 찾은 범위 내에서 이진 탐색을 수행합니다.
  
  

#include <iostream>
#include <algorithm> // std::binary_search

// 이진 탐색 함수
int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // 값을 찾지 못한 경우
}

// 지수 탐색 함수
int exponentialSearch(int arr[], int n, int x) {
    if (n == 0)
        return -1; // 배열이 비어있는 경우

    if (arr[0] == x)
        return 0;

    int i = 1;
    while (i < n && arr[i] <= x)
        i = i * 2;

    return binarySearch(arr, i / 2, std::min(i, n - 1), x);
}

int main() {
    int arr[] = {2, 3, 4, 10, 40, 50, 70, 80, 90, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int index = exponentialSearch(arr, n, x);

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

    return 0;
}

 

출력

 

Element 10 is at index 3

 

 

프로세스 설명

 

• 이진 탐색 함수
  • 'binarySearch' 함수는 주어진 범위 '[left, right]'에서 값을 찾습니다.
  • 중간 값을 계산하고, 그 값이 찾는 값인지 확인합니다.
  • 중간 값이 찾는 값보다 작으면 왼쪽 범위를, 크면 오른쪽 범위를 조정합니다.
  • 값을 찾지 못하면 -1을 반환합니다.
• 지수 탐색 함수
  • 'exponentialSearch' 함수는 배열과 그 크기, 찾고자 하는 값을 인자로 받습니다.
  • 배열의 첫 번째 요소를 검사한 후, 배열을 지수적으로 확장하여 값을 찾을 수 있는 범위를 설정합니다.
  • 그 범위 내에서 이진 탐색을 수행하여 값을 찾습니다.
    
    

마무리

 

지수 탐색은 정렬된 배열에서 매우 효율적인 검색 방법입니다.

특히, 이진 탐색과 결합하여 큰 배열에서도 빠른 검색이 가능합니다.

이 알고리즘은 배열의 특정 요소가 초반부에 위치해 있을 때 더 효과적입니다.

 

 

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