보간 탐색(Interpolation Search)은 선형적으로 분포된 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.보간 탐색은 이진 탐색과 유사하지만, 이진 탐색이 배열의 중간 요소를 기준으로 검색 범위를 줄이는 반면,보간 탐색은 검색 값이 어디에 있을지 추정하여 더 효율적으로 검색 범위를 줄입니다.이는 이진 탐색보다 평균적인 경우에 더 빠를 수 있지만, 최악의 경우 O(n)이 될 수 있습니다.보간 탐색의 시간 복잡도는 일반적으로 O(log(log(n)))입니다. 동작 원리 배열이 정렬되어 있다는 가정 하에, 찾고자 하는 값의 위치를 추정하여 검색 범위를 줄입니다.보간 공식을 사용하여 위치를 계산합니다'pos = low + ((x - arr[low]) * (high - low) / (arr[high]..