[자료구조] 색인 순차 탐색 (indexed sequential search)CSE/자료구조 (data structure)2022. 11. 20. 00:00
Table of Contents
색인 순차 탐색이란?
색인 순차 탐색은 인덱스 테이블을 사용해서 탐색의 효율을 높이는 방법입니다.
인덱스 테이블 (index table)
탐색하려고 하는 리스트의 일정 간격으로 떨어져 있는 요소들을 가지고 온 테이블입니다. 정렬된 리스트의 데이터 수가 $n$개이고, 인덱스 테이블의 크기가 $m$이라면 각 인덱스 항목은 정렬된 리스트의 각 $n/m$번째 데이터를 가지고 있습니다.
색인 순차 탐색 구현
색인 순차 탐색의 핵심은 인덱스 테이블
입니다.
인덱스 테이블에서 찾고자 하는 값이 있는 범위만 조사합니다(index_table[i].key ≤ x < index_table[i + 1].key
). 어느 범위에 있는지 알아냈다면, 해당 범위에서만 순차 탐색을 수행합니다.
코드로 구현하면 다음과 같습니다.
int search_index(int key, int n) {
int low, high;
if(key < list[0] || key > list[n - 1]) {
return -1;
}
for(int i = 0; i < INDEX_SIZE; i++) {
if(index_list[i].key <= key && index_list[i + 1].key > key) {
break;
}
}
if(i == INDEX_SIZE) {
low = index_list[i - 1].index;
high = n;
} else {
low = index_list[i].index;
high = index_list[i + 1].index;
}
return seq_search(key, low, high);
}
색인 순차 탐색의 시간복잡도
정렬된 리스트의 데이터 수가 $n$개이고, 인덱스 테이블의 크기가 $m$이라면 색인 순차 탐색의 시간복잡도는 $O(n + m / m)$입니다.
728x90
반응형
'CSE > 자료구조 (data structure)' 카테고리의 다른 글
[자료구조] AVL 트리 (0) | 2022.11.22 |
---|---|
[자료구조] 보간 탐색 (interpolation search) (0) | 2022.11.21 |
[자료구조] 이진 탐색 (binary search) (0) | 2022.11.19 |
[자료구조] 탐색 (search) (0) | 2022.11.18 |
[자료구조] 기수 정렬 (radix sort) (0) | 2022.11.16 |
@junyeokk :: 나무보다 숲을
컴퓨터 전공 관련, 프론트엔드 개발 지식들을 공유합니다. React, Javascript를 다룰 줄 알며 요즘에는 Typescript에도 관심이 생겨 공부하고 있습니다. 서로 소통하면서 프로젝트 하는 것을 즐기며 많은 대외활동으로 개발 능력과 소프트 스킬을 다듬어나가고 있습니다.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!