Algorithm Guidecomplexity: O(log n)

피보나치 탐색 (Fibonacci Search)

피보나치 수열을 이용해 구간을 분할합니다. 나눗셈 없이 덧셈·뺄셈만으로 인덱스를 계산하므로, 나눗셈이 비싼 하드웨어나 CPU 캐시 친화적 접근이 필요한 환경에서 이진 탐색보다 빠를 수 있습니다.

01피보나치 탐색 (Fibonacci Search)

알고리즘 작동 원리 탐색

피보나치 탐색을 시작합니다. 피보나치 수만큼씩 구간을 갈라, 나눗셈 없이 덧셈과 뺄셈만으로 짚을 자리를 정합니다.

처음 짚은 자리는 인덱스 4, 값은 45입니다. 목표 89와 견줍니다.

45는 89보다 작습니다. 오른쪽만 남기고 피보나치 수를 한 칸 낮춥니다.

다음으로 짚은 자리는 인덱스 7, 값은 78입니다.

78도 89에 못 미칩니다. 다시 오른쪽으로 옮겨 가며 구간을 줄입니다.

이번에 짚은 자리는 배열 끝의 98입니다.

98은 89보다 큽니다. 목표는 왼쪽에 있으니 피보나치 수를 두 칸 낮춰 구간을 크게 줄입니다.

짚은 자리의 값이 89 — 목표와 일치합니다. 네 번 만에 찾았습니다.

탐색 완료 · 89는 인덱스 8에 있습니다. 나눗셈이 비싼 임베디드 환경에서 이진 탐색 대신 씁니다.

Live Python

1def fibonacci_search(arr, target):

2 n = len(arr)

3 fib_m2 = 0

4 fib_m1 = 1

5 fib_m = fib_m2 + fib_m1

# F(k-2): 5

6 while fib_m < n:

# F(k-1): 8

7 fib_m2 = fib_m1

# F(k): 13

8 fib_m1 = fib_m

9 fib_m = fib_m2 + fib_m1

10 offset = -1

11 while fib_m > 1:

12 i = min(offset + fib_m2, n - 1)

13 if arr[i] < target:

14 fib_m = fib_m1

15 fib_m1 = fib_m2

16 fib_m2 = fib_m - fib_m1

17 offset = i

18 elif arr[i] > target:

19 fib_m = fib_m2

20 fib_m1 = fib_m1 - fib_m2

21 fib_m2 = fib_m - fib_m1

22 else:

23 return i

24 return -1

1 / 9

02 쉽게 이해하기

For Everyone

🔑핵심 동작

피보나치 수로 구간을 나눠, 나눗셈 없이 덧셈과 뺄셈만으로 범위를 좁힙니다.

💡쉽게 말하면

피보나치 수열로 구간을 분할해 탐색합니다.

나눗셈 없이 덧셈·뺄셈만 써서 특정 하드웨어에서 유리해요.

📍어디에 쓰나

–나눗셈이 비싼 환경
–캐시 친화적 접근

03 파이썬 구현 코드

피보나치 탐색 (Fibonacci Search)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def fibonacci_search(arr, target):
    n = len(arr)
    fib_m2, fib_m1 = 0, 1
    fib_m = fib_m2 + fib_m1
    while fib_m < n:
        fib_m2, fib_m1 = fib_m1, fib_m
        fib_m = fib_m2 + fib_m1
    offset = -1
    while fib_m > 1:
        i = min(offset + fib_m2, n - 1)
        if arr[i] < target:
            fib_m, fib_m1 = fib_m1, fib_m2
            fib_m2 = fib_m - fib_m1
            offset = i
        elif arr[i] > target:
            fib_m = fib_m2
            fib_m1 -= fib_m2
            fib_m2 = fib_m - fib_m1
        else:
            return i
    return -1