[기초] C++ 피보나치 탐색 (Fibonacci Search)

---

 

피보나치 탐색(Fibonacci Search)은 정렬된 배열에서 특정 값을 찾는 데 사용하는 탐색 알고리즘입니다.

이 알고리즘은 이진 탐색(Binary Search)와 유사하지만,

피보나치 수열을 이용해 비교할 인덱스를 정하는 점에서 차이가 있습니다.

피보나치 탐색은 특히 메모리 계층 구조가 있는 시스템에서 효율적으로 동작합니다.

 

---

 

동작 원리

 

• 피보나치 수열 생성
  
  • 탐색 범위 내에서 사용할 피보나치 수를 계산합니다.
    피보나치 수열은 다음과 같은 점화식으로 정의됩니다.
    • ( F(0) = 0 )
    • ( F(1) = 1 )
    • ( F(n) = F(n-1) + F(n-2) ) (n ≥ 2)
      
      
• 초기 설정
  • 탐색 범위의 크기를 ( N )이라 할 때, ( N )보다 큰 가장 작은 피보나치 수 ( F(k) )를 찾습니다.
  • 초기 값 설정
    • ( F(m) = F(k-1) ), ( F(n) = F(k-2) ), 그리고 ( F(o) = F(k-3) )
  • offset을 -1로 설정합니다.
    offset은 탐색 구간의 시작점을 의미합니다.
    
    
• 반복 탐색
  • 피보나치 수열에 따라 비교할 인덱스를 정합니다
    • ( i = min(offset + F(o), N-1) )
  • 배열의 중간 값과 비교합니다.
    • 만약 찾고자 하는 값이 중간 값보다 작다면, 배열의 앞쪽 부분을 탐색하도록 피보나치 수를 조정합니다.
      • ( F(m) = F(n) )
      • ( F(n) = F(o) )
      • ( F(o) = F(m - n) )
    • 만약 찾고자 하는 값이 중간 값보다 크다면, 배열의 뒷쪽 부분을 탐색하도록 피보나치 수를 조정하고 offset을 변경합니다.
      • ( F(m) = F(n) )
      • ( F(n) = F(o) )
      • ( F(o) = F(m - n) )
      • offset = i
    • 만약 찾고자 하는 값을 찾으면 인덱스를 반환합니다.
      
      
• 결과 반환
  • 값을 찾으면 해당 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다.
    
    

#include <iostream>
#include <vector>
#include <algorithm>  // std::min

int fibonacciSearch(int arr[], int size, int key) {
    // Initialize fibonacci numbers
    int fibMMm2 = 0;   // (m-2)'th Fibonacci No.
    int fibMMm1 = 1;   // (m-1)'th Fibonacci No.
    int fibM = fibMMm2 + fibMMm1;  // m'th Fibonacci

    // Find the smallest Fibonacci number greater than or equal to size
    while (fibM < size) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }

    // Marks the eliminated range from front
    int offset = -1;

    // While there are elements to be inspected, note that we compare arr[fibMMm2] with key
    // When fibM becomes 1, fibMMm2 becomes 0
    while (fibM > 1) {
        // Check if fibMMm2 is a valid location
        int i = std::min(offset + fibMMm2, size - 1);

        // If key is greater than the value at index fibMMm2, cut the subarray array from offset to i
        if (arr[i] < key) {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        }
        // If key is less than the value at index fibMMm2, cut the subarray after i+1
        else if (arr[i] > key) {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        }
        // Element found. Return index
        else return i;
    }

    // Comparing the last element with key
    if (fibMMm1 && arr[offset + 1] == key) return offset + 1;

    // Element not found. Return -1
    return -1;
}

int main() {
    int arr[] = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 85;
    int index = fibonacciSearch(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 85 is at index 8

 

마무리

 

피보나치 탐색은 정렬된 배열에 대해 효율적인 탐색을 제공하며,

특히 메모리 접근 비용이 중요한 경우에 유리합니다.

이 알고리즘은 이진 탐색과 달리 피보나치 수열을 사용하여 탐색 범위를 점진적으로 좁혀나가는 것이 특징입니다.

 

 

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