Fibonacci Search 코드

🎁 피보나치 수열에 대한 설명

정렬 배열에서 대상 값의 위치를 찾는 일반적인 알고리즘

분할 정복 알고리즘을 사용하여 정렬된 배열을 검색하는 방법

📃 Fibonacci Search란?
이진 검색과 비슷한 원리를 사용하지만, 검색 위치를 결정하는 데 사용되는 중간 값(mid) 대신, 피보나치 수열에서의 값을 사용.
이진 검색과 마찬가지로 검색 범위를 반복해서 절반으로 줄여가면서 찾고자 하는 값을 찾음.

해당 알고리즘의 시간 복잡도는 O(log3(n))이고, 공간 복잡도는 O(1)이다.

🔑 Fibonacci Search 원리

1. 먼저, 주어진 배열에서 검색 범위를 결정.
   초기 검색 범위는 전체 배열이다.

2. 이진 검색과 달리, 검색 위치(mid)는 피보나치 수열에서의 값을 사용.
   ==> 검색 범위를 피보나치 수열에서의 값을 사용하여 계속해서 나눠나가면서 검색.

3. 검색 범위 내에서 찾고자 하는 값(key 값)과 mid에 위치한 값을 비교

   • key < mid:
     검색 범위를 앞쪽 부분(작은 쪽)으로 이동합니다. 이 때, mid의 위치는 앞쪽 부분에서 두 번째 피보나치 수열 값의 위치에 있습니다
   • key > mid:
     검색 범위를 뒤쪽 부분(큰 쪽)으로 이동합니다. 이 때, mid의 위치는 뒤쪽 부분에서 첫 번째 피보나치 수열 값의 위치에 있습니다.
   • key == mid:
     검색 종료

💻 코드

🔽 주어진 배열(array)의 길이보다 작은 피보나치 수열 값을 찾음

package com.thealgorithms.searches;

import com.thealgorithms.devutils.searches.SearchAlgorithm;

/*
 *  Fibonacci Search is a popular algorithm which finds the position of a target value in
 *  a sorted array
 * -> 정렬 배열에서 대상 값의 위치를 찾는 일반적인 알고리즘.
 *
 *  The time complexity for this search algorithm is O(log3(n))
 * -> 이 검색 알고리즘의 시간 복잡도는 O(log3(n))
 *  The space complexity for this search algorithm is O(1)
 * -> 이 검색 알고리즘의 공간 복잡도는 O(1)
 *  @author Kanakalatha Vemuru (https://github.com/KanakalathaVemuru)
 */
public class FibonacciSearch implements SearchAlgorithm {

    /**
     * @param array is a sorted array where the element has to be searched
     * -> 요소를 검색해야 하는 정렬된 배열
     * @param key is an element whose position has to be found
     * -> 위치를 찾아야 하는 요소
     * @param <T> is any comparable type
     * @return index of the element
     */
    @Override
    public <T extends Comparable<T>> int find(T[] array, T key) {
        int fibMinus1 = 1; // F_{n-1}
        int fibMinus2 = 0; // F{n-2}
        int fibNumber = fibMinus1 + fibMinus2; // F_{n}=F_{n-1}+F{n-2}
        int n = array.length; // 초기 검색 범위 = 전체 배열

        // 피보나치 수열 값 찾음. 각 값들을 순차적 업데이트
        while (fibNumber < n) {
            fibMinus2 = fibMinus1; // 2 =1
            System.out.print("F{n-2} 확인: " + fibMinus2 + "  ");
            fibMinus1 = fibNumber; // 1 = 1
            System.out.print("F{n-1} 확인: " + fibMinus1 + "  ");
            fibNumber = fibMinus2 + fibMinus1;
            System.out.print("피보나치 수열 진행:" + fibNumber + "  ");
            
            System.out.println();
        } // -> 피보나치 수열 반복.
        System.out.println("fibNumber 최종 돌림:" + fibNumber);
        

📢 출력 결과

---

✅ offset 선언한 이유.
offset 변수는 검색 범위의 시작 위치로 검색 대상 배열의 첫 번째 원소부터 현재 검색 범위의 시작 위치까지의 거리를 나타냄.

        int offset = -1;
        
        // 찾고자 하는 값(key)과 mid에 위치한 값(array[i])을 비교하면서 검색 수행
        while (fibNumber > 1) {
            System.out.println("fibMinus2의 값:" + fibMinus2);
            System.out.println("offset + fibMinus2의 값: " + (offset + fibMinus2));
            int i = Math.min(offset + fibMinus2, n - 1);
            System.out.println("i의 값:" + i);

            System.out.println("array[i].compareTo(key) 확인:" +  array[i].compareTo(key));
            
            /*
             * compareTo:
             * 현 객체: this, 파라메타: obj
             * 1. this < obj ==> 음수리턴
             * 2. this == obj ==> 0 리턴
             * 3. this > obj ==> 양수 리턴.
             */
             
            if (array[i].compareTo(key) < 0) {
                fibNumber = fibMinus1;
                fibMinus1 = fibMinus2;
                fibMinus2 = fibNumber - fibMinus1;
                offset = i;
                System.out.println(
                        "음수 결과 시: " + " fibNumber: " +
                                fibNumber +
                        ". fibMinus1 " +
                        fibMinus1 +
                        " . fibMinus2 " +
                        fibMinus2 +
                        " + offset " +
                        offset
                    );
                System.out.println();
            } else if (array[i].compareTo(key) > 0) {
                fibNumber = fibMinus2;
                fibMinus1 = fibMinus1 - fibMinus2;
                fibMinus2 = fibNumber - fibMinus1;
                System.out.println(
                        "양수 결과 시: " + " fibNumber: " +
                                fibNumber +
                        ". fibMinus1 " +
                        fibMinus1 +
                        " . fibMinus2 " +
                        fibMinus2 
                    );
            } else {
                return i; // this == obj ==> 0 리턴
            }
        }

        if (fibMinus1 == 1 && array[offset + 1] == key) {
            System.out.println("들어왓어?");
            return offset + 1;
        }

        return -1;
    }

📢 출력 결과

---

    // Driver Program
    public static void main(String[] args) {
        Integer[] integers = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

        int size = integers.length;
        Integer shouldBeFound = 128;
        FibonacciSearch fsearch = new FibonacciSearch();
        int atIndex = fsearch.find(integers, shouldBeFound);

        System.out.println(
            "Should be found: " +
            shouldBeFound +
            ". Found " +
            integers[atIndex] +
            " at index " +
            atIndex +
            ". An array length " +
            size
        );
    }
}

📢 출력 결과

출처:
<https://pgh268400.tistory.com/70
https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98>
https://en.wikipedia.org/wiki/Fibonacci_search_technique