[자료구조] 24 보간 탐색

📌보간 탐색 (interpolation search)

항목들이 정렬되어 있을 때 키 값의 차이와 위치의 차이가 비례한다는 가정을 바탕으로 

정렬된 항목 리스트에 대한 것? => 이진 탐색과 유사

단, median값을 이용하는 것이 아닌 탐색 Key와 탐색 경계 값의 차이를 고려하여 키의 위치 결정

 

✔️가정

양쪽 경계 값들의 차이 : 키 값과 왼쪽 경계 값의 차이 = 양쪽 범위의 거리 : 탐색 위치와 왼쪽 경계의 거리 차이 

즉,

👉 ( list[right] - list[left] ) : ( key - list[left] ) = ( right - left ) : ( 탐색위치 - left )

 

계산하면 

👉 pos = left + [( right - left )  *  ( key - list[left] )]  /  [( list[right] - list[left] )]

 

public class Interpolation {
    public static void main(String[] args) {
        int n = 9;
        int pos;
        int key = 23;
        int[] num = {0, 1, 5, 9, 13, 17, 23, 32, 45};

        pos = inter_search(num, key, n);
        if (pos == -1) {
            System.out.println("Cannot find!");
        } else {
            System.out.println(pos);
        }
    }

    public static int inter_search(int num[], int key, int n) {
        int pos;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            pos = left + ((right - left) * (key - num[left])) / (num[right] - num[left]);
            if (num[pos] < key) {
                left = pos + 1;
            } else if (num[pos] > key) {
                right = pos - 1;
            } else if (num[pos] == key){
                return pos;
            }else return -1;
        }
        return -1;
    }
}

//결과 6 출력 
//만약 key= 24라면 결과 cannot find! 출력

100을 Key로 잡으니까 이 탐색 방법의 가정 자체가 비율을 이용하는 것이기 때문에 right(최댓값)에서 

범위 이상으로 넘어가는 수가 key로 잡히게 되면 

"java.lang.ArrayIndexOutOfBoundsException" 오류가 뜨게 된다 💢 조심..