탐색(Search)

효율적인 탐색을 위해서는 어떻게 찾을까만을 고민해서는 안 됩니다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 우선 고민해야 합니다.  보간 탐색(Interpolation Search) 이진 탐색처럼 그냥 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자! 탐색 대상이 존재하지 않을 경우, 탐색 대상의 값은 탐색 범위의 값을 넘어선다는 사실을 근거로 탈출조건을 수정해야 합니다.

#include <stdio.h>
 
int ISearch(int ar[], int first, int last, int 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() {
    int arr[] = { 1,3,5,7,9 };
    int idx;
 
    idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 7);
    if (idx == -1) {
        printf("failed \n");
    }
    else {
        printf("target idx : %d \n", idx);
    }
 
    idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);
    if (idx == -1)
        printf("Failed\n");
    else
        printf("target idx : %d \n", idx);
 
    return 0;
}

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