지금까지 배운 탐색에는 순차 탐색, 이진 탐색이 있다.
순차 탐색 - 정렬되지 않은 대상을 기반으로 하는 탐색
이진 탐색 - 정렬된 대상을 기반으로 하는 탐색
이 중에서 이진 탐색은 중앙에 위치한 데이터를 탐색한 후 이를 기준으로 탐색 대상을 반으로 줄여나가면서 탐색을 진행하는 알고리즘이다. 찾는 대상이 맨 앞에 있던 뒤에 있던 무조건 중앙부터 반씩 줄여가면서 탐색을 진행하는데 이러한 부분에서 효율이 떨어지는 경향이 있다. 이를 개선한 알고리즘이 보간 탐색이다.
보간 탐색은 오름차순으로 정렬된 배열에서 찾고자하는 데이터가 앞에 있으면 앞쪽에서 탐색을 시작한다.
만약 다음 배열에서 key = 25 를 탐색한다고 가정하면
탐색 위치 = low + (key-array[low])/(array[high]-array[low]) x (high - low) 가 된다.
이를 한글로 표현하면
배열 인덱스의 최소값 + (탐색 대상 - 배열의 최소값)/ (배열의 최대값 - 배열의 최소값) x 배열의 인덱스의 최대값 이 된다.
따라서 위 예제를 가지고 풀어보면
라는 값이 나오기 때문에 array[3] 을 탐색해봤더니 target 의 수가 더 크기 때문에
first 에 mid+1 값인 4 , last 에 13 값을 넣어 재귀함수를 통해 다시 구하면 mid 값이 0이 되기 때문에 array[0] 인 25 가 target의 값과 동일하여 탐색이 끝나게 된다.
▼보간 탐색 코드
import java.io.*;
import java.util.*;
public class Main {
public static int Isearch(int arr[],int first, int last, int target) {
int mid;
if(first>last)
return -1;
mid = first + ((target-arr[first])/(arr[last]-arr[first]))
*(last-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);
}
public static void main(String[] args) {
int arr[] = {14,15,27,39,46,47,57,61,65,70,77,79,87,91,99};
int idx = Isearch(arr,0,arr.length-1,46);
if(idx==-1)
System.out.println("탐색 실패");
else
System.out.println("타겟 저장 인덱스 : "+idx);
}
}
결과
타겟 저장 인덱스 : 4
'CS > 자료구조' 카테고리의 다른 글
자료구조 - AVL 트리 (1) | 2024.02.01 |
---|---|
자료구조 - 이진탐색트리 (0) | 2024.01.31 |
자료구조 - 퀵 정렬 (0) | 2024.01.26 |
자료구조 - 병합정렬 (0) | 2024.01.24 |
자료구조 - 힙 정렬 (0) | 2024.01.23 |