Algorithm/Search
2021. 4. 30. 18:43
보간 탐색(Interpolation Search)
이진 탐색이 무조건 가운데를 검사한다는 것을 개선한 방법이다.
가장 높은 값과 가장 낮은 값을 통해 인덱스를 보간한다.
데이터가 균등하게 분포되어 있는 자료에 사용하기 적합하다.
data : 데이터의 집합
low : 가장 낮은 인덱스
high : 가장 높은 인덱스
mid : 비교할 값의 인덱스mid = low + (high - low) * (value - data[low]) / (data[high] - data[low])