[Data Structure] Chapter 11-1: 탐색의 이해와 보간 탐색

데이터를 찾는 방법인 탐색에 대해 이해하고, 보간 탐색을 구현해보자.

 

 

탐색의 이해

• 탐색: '데이터를 찾는 방법'을 의미한다. 이전에 배운 '순차 탐색(linear search)'이나 '이진 탐색(binary search)'가 이에 해당한다.
• 효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민하기 전에, '효율적인 탐색을 위한 저장방법이 무엇일까'를 고민해야 한다.
• 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다.

 

보간 탐색

• 보간 탐색(Interpolation Search): 찾는 대상의 위치를 고려하지 않고 일관적으로 절반씩 줄여나가며 탐색을 진행하는 '이진 탐색'의 비효율성을 개선시킨 알고리즘이다.

 

정수 12를 찾을 때, 보간 탐색과 이진 탐색의 탐색위치

 

low와 high는 탐색대상의 시작과 끝 인덱스, s는 찾는 데이터가 저장된 위치의 인덱스

 

 

보간 탐색의 구현

#include <stdio.h>

int Isearch(int ar[], int first, int last, int target)
{
    printf("first: %d, last: %d, target:%d ", first, last, target);

    int mid;
    if(ar[first]>target || ar[last]<target)
        return -1;

    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);
}

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

    idx = Isearch(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    idx = Isearch(arr, 0, sizeof(arr)/sizeof(int)-1, 2);
    if(idx == -1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    return 0;
}

first: 0, last: 4, target:7 타겟 저장 인덱스: 3 
first: 0, last: 4, target:2 first: 1, last: 4, target:2 탐색 실패

 

-> 원래 이진 탐색 구현의 제한 조건인 first>last를 그대로 사용하면 mid의 조건이 다르기 때문에 무한 루프가 걸릴 수 있음

 

 

---

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11