자료구조_검색 ④ 보간검색

 

 

 

 

[1] 보간 검색

---

(1) 보간검색 개요 

제어검색의 종류 

데이터의 개수와 찾는 값의 성질에 따라 있음직한 위치를 처음 검색위치로 지정하는 방식 

성능 : 이진검색  < 피보나치검색 <보간검색

 

(2)보간 검색 과정

1부터 20까지 있는 데이터에서 찾는 값이 10이라면 

있음직한 위치는 10-1/20-1 x 20 =10 으로 10번째 데이터부터 검색하여 찾는다 

만약 찾는 값이 19라면 

있음직한 위치는 19-1 /20-1 x 20 =18으로 18번째 데이터부터 검색하여 찾고 

없다면 1~18번은 버리고 19.20 위치의 데이터와 비교하여 찾는다