[자료구조][C언어] 보간 탐색

시작하기 앞서 효율적인 탐색방법 뿐만 아니라 효율적인 저장방법을 고민해봐야 한다, 그 방법은 대표적으로 '트리'가 있다. 그렇기 때문에 '트리'에 관한 지식이 부족하다면 다시 한번 공부하고 오길 바란다. 이진 탐색과 보간 탐색 이진 탐색으로 부터 파생된 보간 탐색 오늘 우리가 배울 보간 탐색은 이진 탐색의 과정과 비슷하다. 이진 탐색의 과정에 대해 간단히 설명하면, 먼저 중앙에 위치한 데이터를 탐색한 후, 이를 기준으로 탐색대상을 절반씩 줄여나가며 탐색한다. 이진 탐색의 특징은 찾는 대상의 위치와 상관없이 항상 중앙을 기준으로 절반씩 줄여가면서 탐색을 한다는 것이다. 그렇기 때문에 찾는 대상의 위치에 따라 효율성이 달라지는데, 이를 개선시킨 것이 보간 탐색이다. 보간 탐색은 찾는 대상의 상대적인 위치를 고려해서 탐색대상을 나누어 탐색을 진행한다. 즉, 보간 탐색과 이진 탐색의 차이는 탐색을 어디서부터 시작하냐의 차이인 것이다. (탐색 대상의 맨 앞·맨 뒤·찾는 대상의 위치를 각각 l...

원문링크 : [자료구조][C언어] 보간 탐색