41. 탐색 (2)

피보나치 탐색

피보나치 탐색은 피보나치 수열을 이용하는 탐색 방법이다.

 

int fiboSearch(int arr[], int n, int key){
    int fib2 = 0, fib1 = 1, fib = fib2 + fib1;
    int i, offset = -1;
    
    while (fib < n){
        fib2 = fib1;
        fib1 = fib;
        fib = fib2 + fib1;
    }
    while(fib > 1){
        i = (offset + fib2) < (n - 1) ? offset + fib2 : n - 1;
        if(arr[i] < key){
            fib = fib1;
            fib1 = fib2;
            fib2 = fib - fib1;
            offset = i;
        }
        else if (arr[i] > key){
            fib = fib2;
            fib1 = fib1 - fib2;
            fib2 = fib - fib1;
        }
        else
            return i;
    }
    
    if(fib1 == 1 && arr[offset + 1] == key)
        return offset + 1;
    return -1;
}

---

보간 탐색

보간탐색은 예측을 이용하는 탐색 방법이다.

배열의 값을 보간하여 특정 값이 위치할 것으로 예측하고, 그에 따라 탐색 범위를 좁혀가는 방식이다.

int interpolationSearch(int arr[], int n, int key){
    int low = 0, high = n - 1, pos;
    
    while(low <= high && key >= arr[low] && key <= arr[high]){
        if(low == high){
            if(arr[low] == key) return low;
            return -1;
        }
        pos = low + (((double)(high - low) / (arr[high] - arr[low])) * (key - arr[low]));
        
        if (arr[pos] == key)    return pos;
        else if (arr[pos] < key) low = pos + 1;
        else high = pos - 1;
    }
    return -1;
}