보간 탐색(Interpolation Search)

보간 탐색(Interpolation Search)

• 이진 탐색이 무조건 가운데를 검사한다는 것을 개선한 방법이다.
• 가장 높은 값과 가장 낮은 값을 통해 인덱스를 보간한다.
• 데이터가 균등하게 분포되어 있는 자료에 사용하기 적합하다.

  mid = low + (high - low) * (value - data[low]) / (data[high] - data[low]) 

  
• data : 데이터의 집합
  low : 가장 낮은 인덱스
  high : 가장 높은 인덱스
  mid : 비교할 값의 인덱스

---

참고

• https://jackpot53.tistory.com/35