[자료구조] 보간탐색 알고리즘

보간탐색은 이진탐색과 비슷하다.

이진탐색처럼 배열은 오름차순 나열이 되어있어야한다.

인덱스는 거리를 비교하여 구한다.

배열의 값은 유일하다.

* mid값을 어떻게 구할까?

arr[first]          arr[s]                 arr[last]

   l----------------l--------------------l

이런 긴 배열에서 s라는 인덱스를 찾아야한다.

arr[last]-arr[first]의 길이는 last-first와 같다고 할 수 있다.

arr[s]-arr[first]의 길이는 s-first와 같다고 할 수 있다.

그렇다면 arr[last]-arr[first] : arr[s]-arr[first] = last-first : s-first이다.

A : B = last-first : s - first로 고쳐보면

A(last-first) = B(s-first)이다.

A/B*(last-first)+first = s 라는 것을 찾을 수 있다.

그렇다면 (arr[last]-arr[first])/(arr[s]-arr[first])*(last-first)+first = s 이다.

s는 mid이므로 인덱스 값이 된다.

#include <stdio.h>

int search(int arr[], int first, int last, int target){

int mid;

if(arr[first] > target || arr[last] < target){  // 탈출조건이 이진탐색과 약간 다르다.

return -1;

}

mid = ((double)(target-arr[first])/(arr[last]-arr[first])*(last-first))+first;  // mid 인덱스를 구하는 수식이다.

if(arr[mid] == target){

return mid;

}else if(arr[mid] > target){

return search(arr, first, mid-1, target);

}else{

return search(arr, mid+1, last, target);

}

}

int main(){

int arr[]= {1,5,6,7,9,10};

int index;

index = search(arr, 0, sizeof(arr)/sizeof(int)-1, 7);  // 배열, 첫번쨰 인덱스, 마지막 인덱스, 타겟을 넘겨준다.

if(index == -1){

puts("없음");

}else{

printf("저장 인덱스 %d \n", index);

}

return 0;

}