반응형 InterporlationSearch1 [자료구조] 보간 탐색(Interpolation Search 보간 탐색은 이진탐색과 유사하다. 이진 탐색은 정렬된 배열의 중앙에 위치한 데이터를 기준으로 탐색을 시작한다. 보간탐색은 이런한 방식에서 발생할 수 있는 비효율을 줄이기 위해 등장하였다. 탐색 기준 선정방식 중복된 키가 없이 정렬된 데이터 들에 대한 탐색이라는점을 고려하여 탐색할 대상이 대략적으로 어디에 위치해 있는지를 파악하는 식이 존재한다. 이는 데이터의 값과 그 데이터가 저장된 위치의 인덱스값이 비례하다는 생각을 근거를 기반에 두고있다. "x" 라는 데이터를 찾는 경우, 해당 데이터의 인덱스 값 "s"에 대한 식은 다음과 같다. low : 탐색 대상의 시작 인덱스 high : 탐색 대상의 마지막 인덱스 #include int ISearch(int ar[], int first, int last, in.. 2024. 1. 16. 이전 1 다음 반응형