색인 순차 검색(index sequential search)

<색인 순차 검색(index sequential search)>
​

정렬되어있는 자료에 대한 인덱스 테이블(index table)을 추가로 사용하여 탐색 효율을 높인 검색 방법이다. 

[인덱스 테이블]
배열에 정렬되어있는 자료 중에서 일정한 간격으로 떨어져있는 원소들을 저장한 테이블이다. 자료가 저장되어있는 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, 배열에서 n/m간격으로 떨어져있는 원소와 그의 인덱스를 인덱스 테이블에 저장한다. 

[검색 방법]
indexTable[i].key ≤ key < indexTable[i+1].key를 만족하는 i를 찾아서 배열의 어느 범위에 있는지를 먼저 알아낸 후에 해당 범위에 대해서만 순차 검색 수행

 

예)

검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29}
크기가 3인 인덱스 테이블 작성
인덱스 테이블에서 먼저 탐색키를 검색하여 검색 범위를 확인하고, 해당 범위에 대해서만 순차 검색 실행

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)