목록interpolation search (1)

개발자로 살아남기

[JAVA] 보간 탐색 (Interpolation Search)

보간 탐색 (Interpolation Search) 보간 탐색 (Interpolation Search) 균일하게 n개의 데이터가 분포되어 정렬된 배열이 있을 경우 이진 탐색보다 성능이 좋음 ex) 10, 12, 13, 15, 18, 22, 25, 26, 27, 30, ... => 성능 ↑ 10, 102, 192, 375, 462, 1777, ... => 성능 ↓ 이진 탐색은 탐색 대상의 값과 상관없이 무조건 절반씩 잘라서 비교하지만, 보간 탐색은 탐색 대상이 앞쪽에 있을 경우 앞쪽부터 탐색을 진행 선형 보간법을 이용해 탐색 위치를 결정함 보간 탐색 방법 탐색을 시작할 위치를 공식을 통해 알아낸다. 해당 위치에 탐색 대상이 있을 경우 해당 위치 값을 반환한다. 해당 위치의 값이 탐색 대상보다 작으면 탐색 ..
0x20. 알고리즘/0x21. 이론 2021. 11. 16. 12:28
이전 Prev 1 Next 다음