[20210929] 보간 검색 알고리즘

package Practice;

import java.util.Scanner;

public class InterpolationSearch {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		System.out.println("배열의 크기를 입력하세요.");
		
		int size = sc.nextInt();
		int[] arr = new int[size];
		
		for (int i=0; i<arr.length; i++) {
			System.out.println("arr[" + i + "]에 해당하는 숫자를 입력하세요");
			arr[i] = sc.nextInt();
		}
		
		System.out.println("찾으려는 숫자를 입력하세요.");
		
		int key = sc.nextInt();
		int low = 0;
		int high = arr.length - 1;
		int res = -1;

		while (low <= high) {
			int middle = (key - arr[low]) / (arr[high] - arr[low]) * (high - low) + low;

			if (arr[middle] < key) {
				low = middle + 1;
			}

			else if (arr[middle] > key) {
				high = middle - 1;
			}

			else {
				res = middle;
				break;
			}
		}

		if (res == -1) {
			System.out.println("검색 결과가 없습니다.");
		}

		else {
			System.out.println(res + "에 위치합니다.");
		}
		sc.close();
	}
}