열혈 자료구조 - 11.1 탐색의 이해와 보간 탐색

탐색의 이해

- 효율적인 탐색을 위해서는 찾는 방법뿐 아니라 저장 방법을 고민해야 함

- 효율적인 탐색이 가능한 대표적인 자료구조는 트리

 

보간 탐색

- 정렬이 된 데이터에서 대상에 비례하여 위치를 예측하여 그 위치에서 데이터를 찾는 방법

- 위치를 예측하면 정확하지는 않을 수 있지만 많은 수의 데이터를 배제시킬 수 있음

- 위치를 계산하기 위한 연산에 대한 비용이 추가됨

- 위치를 계산하기 위한 비례식 구성

    -> 데이터를 완전히 비례한다고 가정하고 식을 구성

x = 실제 얻고자 하는 값

    -> 위 계산에 x에 실제 찾고자하는 값을 넣으면 탐색 위치의 인덱스 s를 구할 수 있음

- 보간 탐색의 구현

int ISearch(int ar[], int first, int last, int target)
{
    int mid;

    if(ar[first]>target || ar[last]<target) { return -1; }
        // 탈출조건 : 정렬이 되어있기 때문에 target이 arr[first] 
        // 보다 크거나 ar[last]보다 작으면 찾지 못한 경우 

    mid = ((double)(target-ar[first]) / (ar[last]-ar[first]) * (last-first)) + first;
        // 위에서 구한 비례식
        // 이진트리에서는 간단하게 가운데 인덱스 값을 기준으로 사용했지만
        // 보간탐색에서는 위의 식으로 구한 인덱스를 기준으로 잡음

    if(ar[mid] == target) {
		return mid;    // 탐색된 타겟의 인덱스 값 반환
    }
    else if(target < ar[mid]) {
		return ISearch(ar, first, mid-1, target);
    }
    else {
		return ISearch(ar, mid+1, last, target);
    } // 재귀적으로 호출(이진탐색과 동일)
}