[알고리즘] 색인 순차 검색 (Index Sequential Search) - JAVA / 자바

색인 순차 검색(Index Sequential Search)

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

* 인덱스 테이블 : 배열에 정렬되어 있는 자료 중 일정한 간격으로 떨어져 있는 원소들을 저장한 테이블

    ㄴ 자료가 저장되어 있는 배열의 크기가 n이고 인텍스 테이블의 크기가 m일 때, 배열에서 n/m간격으로 떨어져 있는 원소와 그의 인덱스를 인덱스 테이블에 저장

---

검색 방법

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

 

Ex) 리스트 = {1, 3, 10, 23, 29, 33, 45, 50}

1

3

10

23

29

33

45

50

1. 크기가 3인 인덱스 테이블 (indexTable)

0	1
3	23
7	50

2. 크기가 4인 인덱스 테이블 (indexTable)

0	1
2	10
4	29
7	50

---

검색 성능

 - 인덱스 크기에 따라 다름

    ㄴ 인덱스 테이블의 크기가 줄어들면 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 검색해야 하는 범위 커짐

    ㄴ 인덱스 테이블의 크기를 늘리면 배열의 인덱스를 저장하는 간격이 작아지므로 배열에서 검색해야 하는 범위 작아짐. 대신에 인덱스 테이블 검색 시간 증가

 

 - 시간 복잡도 : O(m + n/m)

    ㄴ 배열의 크기 = n, 인덱스 테이블의 크기 = m