Algorithm Guidecomplexity: O(log n)

피보나치 탐색 (Fibonacci Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Fibonacci Search

피보나치 탐색 시작. 피보나치 수열로 배열을 분할하며, 나눗셈 없이 덧셈·뺄셈만 사용해 CPU 캐시에 유리합니다.

Logic Node1 / 9

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

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