[Programming/Algorithm] 탐색의 이해와 보간 탐색

탐색의 이해

탐색은 '데이터를 찾는 방법'이다. 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 이유는 다음과 같다.

"효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다."

그런데 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 때문에 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다.

정렬도 탐색을 목적으로 하는 경우가 대부분일 만큼 탐색은 자료구조에서, 컴퓨터 공학에서 매우 중요한 위치를 차지하고 있다.

---

보간 탐색(Interpolation Search)

• 정렬되지 않은 대상을 기반으로 하는 탐색 : 순차 탐색
• 정렬된 대상을 기반으로 하는 탐색 : 이진 탐색

이 중에서 이진 탐색은 중앙에 위치한 데이터를 탐색한 후, 이를 기준으로 탐색대상을 반씩 줄여나가면서 탐색을 진행하는 알고리즘이다. 찾는 대상이 중앙에 위치하건 맨 앞에 위치하건 그에 상관하지 않고 일관되게 반씩 줄여가면서 탐색을 진행해 나간다.
때문에 찾는 대상의 위치에 따라서 탐색의 효율에 차이가 발생한다. 그러나 보간 탐색은 이러한 이진 탐색의 비효율성을 개선시킨 알고리즘이다. 개선의 원리는 다음과 같다.

"이진 탐색처럼 그냥 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작한다."

예를 들어 오름차순으로 정렬된 배열을 대상으로 앞쪽에 위치한 데이터를 찾고자 할 때, 이진 탐색과 보간 탐색의 첫 번째 탐색위치는 다음과 같이 차이가 난다.

보간 탐색 vs 이진 탐색

위 그림에서는 정수 12를 찾을 때의 첫 번째 탐색위치를 보여준다. 이진 탐색은 값에 상관없이 탐색 위치를 결정하지만, 보간 탐색은 그 값이 상대적으로 앞에 위치한다고 판단을 하면 앞쪽에서 탐색을 진행한다.
따라서 '데이터'와 데이터가 저장된 위치의 '인덱스 값'이 직선의 형태로 비례하면, 위 그림의 경우와 같이 보간 탐색의 경우 단번에 데이터를 찾기도 한다. 
단번에 찾지 못하더라도 탐색의 위치가, 찾는 데이터와 가깝기 때문에 탐색대상을 줄이는 속도가 이진 탐색보다 뛰어나다.

비례 관계

위 그림에서 low와 high는 탐색대상의 시작과 끝에 해당하는 인덱스 값이고, s는 찾는 데이터가 저장된 위치의 인덱스 값이다. 그런데 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정하기 때문에, 위 그림을 근거로 다음의 비례식을 구성한다.

A : Q = (high - low) : (s - low)

이 식에서 s는 찾고자 하는 데이터의 인덱스 값이므로, 위의 비례식을 s에 대한 식으로 다음과 같이 정리해야 한다.

s = Q / A * (high - low) + low

그리고 찾는 데이터의 값 arr[s]를 x라 하면, 위의 식은 최종적으로 다음과 같이 정리가 된다.

s = (x - arr[low]) / (arr[high] - arr[low]) * (high - low) + low

이로써 찾는 값을 x에 삽입하여 탐색위치 s를 구사는 식이 완성되었다. 이 식은 단순하지만 나눗셈 연산이 들어간다는 사실에 주목해야 한다. 특히 오차율을 최소화하기 위해서 정수형 나눗셈이 아닌 실수형 나눗셈을 진행한다는 사실에 더 주목할 필요가 있다. 이는 보간 탐색의 단점이기 때문이다.

---

보간 탐색의 구현

이론적으로 보간 탐색과 이진 탐색의 유일한 차이점은 탐색의 대상을 선정하는 방법에 있다.

int BSearchRecur(int arr[], int first, int last, int target) {
    if (first > last) {
        return -1;
    }

    int mid = (first + last) / 2;

    if (arr[mid] == target) {
        return mid;
    }
    else if (target < arr[mid]) {
        return BSearchRecur(arr, first, mid - 1, target);
    }
    else {
        return BSearchRecur(arr, mid + 1, last, target);
    }
}

위 예제의 BSearchRecur 함수는 다음 문장을 통해 탐색의 위치를 계산한다.

mid = (first + last) / 2;

그런데 이진 탐색과 보간 탐색의 유일한 차이점은 탐색의 대상을 선택하는 방법에 있다. 이를 다음과 같이 바꾸면, 이로써 보간 탐색의 구현은 완료가 된다.

mid = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

위의 문장에서는 나눗셈의 피연산자를 double형으로 형 변환하여, 모든 연산들이 실수형으로 진행되어 오차가 최소화되도록 하였다. 그리고 이 문장은 위에서 보인 다음 수식을 단순히 코드로 옮긴 것에 지나지 않는다. 위 문장의 target이 아래 수식의 x에 해당하고, 위 문장의 mid가 아래 수식의 s에 해당한다.

s = (x - arr[low]) / (arr[high] - arr[low]) * (high - low) + low

때문에 식을 바꾼 이 시점에서 변수의 이름 mid는 그 이름을 달리해야 한다(더 이상 mid가 중간을 가리키지 않으므로).

#include <iostream>
#include <cstdlib>

using std::cout;
using std::cin;
using std::endl;


int ISearch(int arr[], int first, int last, int target) {
    if (first > last) {
        return -1;
    }

    int mid = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

    if (arr[mid] == target) {
        return mid;
    }
    else if (target < arr[mid]) {
        return ISearch(arr, first, mid - 1, target);
    }
    else {
        return ISearch(arr, mid + 1, last, target);
    }
}


int main() {
    int arr[] = { 1, 3, 5, 7, 9 };
    int len = sizeof(arr) / sizeof(int);
    int idx;

    idx = ISearch(arr, 0, len - 1, 7);
    if (idx == -1) {
        cout << "탐색 실패" << endl;
    }
    else {
        cout << "타겟 저장 인덱스: " << idx << endl;
    }

    idx = ISearch(arr, 0, len - 1, 10);
    if (idx == -1) {
        cout << "탐색 실패" << endl;
    }
    else {
        cout << "타겟 저장 인덱스: " << idx << endl;
    }

    return 0;
}


/* 결과

타겟 저장 인덱스: 3
탐색 실패

*/

실행결과를 보면 배열에 저장된 7은 찾고 배열에 저장되지 않은 10은 찾지 못함을 확인할 수 있다. 따라서 위의 함수 ISearch는 보간 탐색을 제대로 구현한 것처럼 보인다. 하지만 약간의 문제가 있다. 문제의 확인을 위해 다음 main 함수를 대상으로 ISearch함수의 호출결과를 확인해보자.

int main(void) {
  int arr[] = {1, 3, 5, 7, 9};
  int len = sizeof(arr) / sizeof(int);
  int idx;
  
  // 배열에 저장되어 있지 않은 2를 찾기 위해서 ISearch 함수를 호출한다.
  idx = ISearch(arr, 0, len - 1, 2);
  ...
}

위의 main함수를 대상으로는 ISearch 함수가 제대로 동작하지 않음을 확인할 수 있다. 문제는 ISearch 함수의 다음 탈출조건을 만족시키지 못해서 발생한 것이다.

if(first > last) {
  return -1;
}

ISearch 함수의 탈출조건은 다음과 같이 바꿔야 한다.

if(arr[first] > target || arr[last] < target) {
  return -1;
}

탐색대상이 존재하지 않는 경우, ISearch 함수가 재귀적으로 호출됨에 따라 target에 저장된 값은 first와 last가 가리키는 값의 범위를 넘어서게 된다. 다시 말해서, target에 저장된 값이 first가 가리키는 값보다 작거나 last가 가리키는 값보다 커지게 된다.

그리고 그 이유는 단순하다. 정렬된 탐색대상의 범위를 조비혀가면서 정렬을 진행해 나가기 때문이다. first와 last가 target을 향해서 점점 좁혀가므로 이러한 특성을 기반으로 위와 같이 탈출조건을 구성해야 한다.

---

탈출조건을 만족하지 않는 이유

먼저 탈출조건이 만족되지 않는 상황에 대해 예를 들어보자. 다음과 같이 ISearch함수가 호출되었다고 가정해보자.

int main(void) {
  int arr[] = {1, 3, 5, 7, 9};
  ...
  ISearch(arr, 1, 4, 2);    // 배열 arr의 인덱스 1~4 범위 내에서 숫자 2 탐색
}

위와 같이 ISearch 함수가 호출되는 상황은 필요에 의해 만들 수도 있지만 재귀함수의 호출과정에서 만들어질 수도 있다. 그럼 이를 대상으로 탐색위치를 계산하는 다음 문장에 값을 대입해보자. 참고로 first와 last는 각각 1과 4이고 target은 2이다.

mid = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

위의 식에 값을 대입해보면 mid에 0이 저장됨을 확인할 수 있다. 그리고 이는 지극히 정상이다. 인덱스 1~4의 범위 내에서 최댓값과 최솟값은 각각 3과 9이다. 그런데 타겟은 2이다. 즉, 그 값이 탐색 범위 내에 위치하지 못할 만큼 작다. 그러니 가장 왼쪽에 있는 값과 비교를 하라는 의미로 0을 반환하는 것이 타당하다. 여기까지는 문제가 없다. 하지만 이 결과가 다음 문장과 결합되면서 문제가 된다.

...
else {
  return ISearch(arr, mid + 1, last, target);
}

조건에 의해서 마지막 else 구문의 ISearch 함수 호출문이 실행된다. 그리고 그 결과 다시 한번 다음과 같이 ISearch 함수에 인자가 전달된다.

// 이전 호출문과 인자의 전달이 동일하다.
ISearch(arr, 1, 4, 2);

이렇듯 함수의 전달인자는 ISearch 함수의 탈출조건을 만족하지 못하면서, 동일한 전달인자를 가지고 또 다시 ISearch 함수를 호출하는 것이 문제이다. 그래서 위의 예제에서는 '탐색대상이 존재하지 않을 경우, 탐색대상의 값은 탐색범위의 값을 넘어선다'는 사실을 근거로 탈출조건을 다음과 같이 수정해야 한다.

if(arr[first] > target || arr[last] < target) {
  return -1;
}

최종적인 코드

#include <iostream>
#include <cstdlib>

using std::cout;
using std::cin;
using std::endl;


int ISearch(int arr[], int first, int last, int target) {
    if(arr[first] > target || arr[last] < target) {
        return -1;
    }

    int mid = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

    if (arr[mid] == target) {
        return mid;
    }
    else if (target < arr[mid]) {
        return ISearch(arr, first, mid - 1, target);
    }
    else {
        return ISearch(arr, mid + 1, last, target);
    }
}


int main() {
    int arr[] = { 1, 3, 5, 7, 9 };
    int len = sizeof(arr) / sizeof(int);
    int idx;

    idx = ISearch(arr, 0, len - 1, 7);
    if (idx == -1) {
        cout << "탐색 실패" << endl;
    }
    else {
        cout << "타겟 저장 인덱스: " << idx << endl;
    }

    idx = ISearch(arr, 0, len - 1, 2);
    if (idx == -1) {
        cout << "탐색 실패" << endl;
    }
    else {
        cout << "타겟 저장 인덱스: " << idx << endl;
    }

    return 0;
}


/* 결과

타겟 저장 인덱스: 3
탐색 실패

*/

---

탐색 키(Search Key)와 탐색 데이터(Search Data)

// 탐색 키에 대한 typedef 선언
typedef int Key;

// 탐색 데이터에 대한 typedef 선언
typedef double Data;

typedef struct item {
  Key searchKey;    // 탐색 키(search key)
  Data searchData;  // 탐색 데이터(search data)
} Item;

다음 문장이 말하는 방식으로의 탐색이 의미 있는 탐색이라 할 수 있다.

"사번이 5인 직원의 정보를 찾는다."

이때 사번이 '탐색 키(search key)'가 되고, 직원의 정보가 '탐색 데이터(search data)'가 된다. 때문에 일반적인 상황에서는 위의 구조체 정의에서 보이듯이 탐색 키와 탐색 데이터를 묶는 형태의 구조체를 정의하게 되고, 정렬이나 탐색이나 그 탐색의 대상을 탐색 키에 맞추게 된다.

이는 컴퓨터 공학에서 말하는 '키'의 기본 개념이다. 즉 키에는 그 값이 유일하다는 의미가 담겨 있고 null과 같은 값이 채워질 수 없다는 의미도 담겨 있다. 따라서 다음과 같은 질문은 잘못된 것이다.

"찾고자 하는 키의 값이 두 개 이상 존재할 때는 무엇을 찾아야 할까?"

위의 상황에서의 키는 더 이상 키라고 할 수 없다. 따라서 이 경우에는 키가 될 수 있는 대상을 잘못 선택한 결과로 판단해야 옳다. 예외라고 판단하는 상황의 대부분은 그저 판단의 잘못일 뿐 예외가 아니다.