자료구조 - 색인 순차 탐색

[색인 순차 탐색 (Indexed Sequential Search)]

색인 순차 탐색은 순차 탐색과 색인을 결합한 탐색 알고리즘으로, 데이터가 정렬되어 있는 경우 색인을 사용해 탐색 범위를 좁혀 탐색 시간을 단축할 수 있습니다.

큰 데이터셋을 작은 블록으로 나누고, 각 블록의 시작 지점에 대한 색인을 만들어서 탐색 성능을 향상시킵니다.

 

 

색인 순차 탐색 작동 원리

1. 색인 생성: 데이터를 일정한 크기의 블록으로 나누고, 각 블록의 첫 번째 요소를 색인 테이블에 저장합니다.
2. 색인 탐색: 색인 테이블을 순차 탐색하여 찾고자 하는 값이 속할 가능성이 있는 블록을 찾습니다.
3. 블록 탐색: 해당 블록 내에서 순차 탐색을 수행하여 값을 찾습니다.

 

 

색인 순차 탐색 의사 코드

함수 indexedSequentialSearch(arr, n, key, blockSize):
    // 색인 생성
    indexTable = []
    for i from 0 to n-1 step blockSize:
        indexTable.append((arr[i], i))
    
    // 색인 탐색
    for i from 0 to len(indexTable)-1:
        if key < indexTable[i].first:
            blockStart = indexTable[i-1].second
            blockEnd = min(indexTable[i].second, n)
            break
        else if key == indexTable[i].first:
            반환 indexTable[i].second
    
    // 블록 탐색
    for j from blockStart to blockEnd-1:
        if arr[j] == key:
            반환 j
    
    반환 -1 // key를 찾을 수 없는 경우

 

 

 

색인 순차 탐색 예제

정렬된 배열: [11, 22, 25, 45, 64]
찾고자 하는 값: 22
블록 크기: 2

1. 색인 생성:
    색인 테이블: [(11, 0), (25, 2), (64, 4)]

2. 색인 탐색:
    22는 11과 25 사이에 있으므로, 블록 [11, 22]에서 탐색
    블록의 시작 지점: 0
    블록의 끝 지점: 2

3. 블록 탐색:
    순차 탐색: 11, 22
    값 22를 찾음

 

 

 

색인 순차 탐색 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 색인 순차 탐색 함수
int indexedSequentialSearch(const vector<int>& arr, int key, int blockSize)
{
    // 색인 생성
    vector<pair<int, int>> indexTable;
    for (int i = 0; i < arr.size(); i += blockSize) 
    {
        indexTable.push_back({arr[i], i});
    }
    
    // 색인 탐색
    int blockStart = 0;
    int blockEnd = arr.size();
    for (int i = 0; i < indexTable.size(); ++i) 
    {
        if (key < indexTable[i].first) 
        {
            blockStart = indexTable[i - 1].second;
            blockEnd = min(indexTable[i].second, (int)arr.size());
            break;
        }
        else if (key == indexTable[i].first) 
        {
            return indexTable[i].second;
        }
    }

    // 블록 탐색
    for (int j = blockStart; j < blockEnd; ++j)
    {
        if (arr[j] == key)
        {
            return j;
        }
    }
    
    return -1; // key를 찾을 수 없는 경우
}

int main() 
{
    vector<int> arr = {11, 22, 25, 45, 64}; // 정렬된 예제 배열
    int key = 22; // 찾고자 하는 값
    int blockSize = 2; // 블록 크기

    // 색인 순차 탐색 수행
    int result = indexedSequentialSearch(arr, key, blockSize);

    // 결과 출력
    if (result != -1) 
    {
        cout << "값 " << key << "을(를) 인덱스 " << result << "에서 찾았습니다." << endl;
    } 
    else 
    {
        cout << "값 " << key << "을(를) 배열에서 찾을 수 없습니다." << endl;
    }

    return 0;
}

 

 

 

색인 순차 탐색 장단점

 

장점 :

1. 효율성: 순차 탐색보다 더 빠릅니다. 특히 데이터셋이 큰 경우에 유용합니다.
2. 간단한 구현: 색인을 추가하는 것만으로도 성능이 향상됩니다.

단점 : 

1. 추가 메모리 사용: 색인 테이블을 저장하기 위한 추가 메모리가 필요합니다.
2. 정렬 필요: 데이터가 미리 정렬되어 있어야 합니다.
3. 효율성 저하: 블록 크기가 부적절하게 설정되면 성능이 크게 저하될 수 있습니다.

 

 

시간 복잡도

인덱스 테이블의 크기를 m 이라고 하고, 자료 리스트의 크기를 n 이라고 하면 

색인 순차 탐색의 시간 복잡도는 O(m+n/m) 입니다.