검색 알고리즘 개요

대규모 데이터 처리 환경에서 검색 연산은 핵심적인 작업이며, 효율적인 알고리즘은 시스템 자원과 시간을 절약합니다. 본 문서는 세 가지 기본 검색 기법을 분석합니다.

순차 검색

가장 단순한 검색 방식으로, 데이터 정렬이 필요 없으며 모든 요소를 순차적으로 비교합니다. 시간 복잡도: O(N)

#define SIZE 10

int sequential_find(int *dataset, int size, int target) {
    for(int idx = 0; idx < size; idx++) {
        if(target == dataset[idx])
            return idx;
    }
    return -1;
}

이진 검색

정렬된 데이터 집합에 적용 가능한 고속 검색 기법입니다. 중간값 비교를 통해 검색 범위를 반으로 축소합니다. 시간 복잡도: O(logN)

선행 정렬을 위한 선택 정렬:

void selection_sort(int *dataset, int size) {
    for(int i = 0; i < size-1; i++) {
        int min_idx = i;
        for(int j = i+1; j < size; j++) {
            if(dataset[j] < dataset[min_idx])
                min_idx = j;
        }
        int temp = dataset[i];
        dataset[i] = dataset[min_idx];
        dataset[min_idx] = temp;
    }
}

반복적 이진 검색:

int iterative_binary_find(int *dataset, int size, int target) {
    int left = 0;
    int right = size - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(dataset[mid] == target) 
            return mid;
        if(target < dataset[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

재귀적 이진 검색:

int recursive_find(int *dataset, int left, int right, int target) {
    if(left > right) return -1;
    int mid = (left + right) / 2;
    if(dataset[mid] == target) return mid;
    if(target < dataset[mid]) 
        return recursive_find(dataset, left, mid-1, target);
    else 
        return recursive_find(dataset, mid+1, right, target);
}

블록 검색

대용량 데이터 처리 시 분할 정복 접근법입니다. 데이터를 논리적 블록으로 분할한 후, 대상 블록에서만 검색을 수행합니다. 사전 검색이 대표적 예시입니다.

해시 검색

해시 함수를 이용한 O(1) 시간 복잡도 검색 기법입니다. 데이터 값을 해시 테이블 인덱스로 변환하며, 공간 복잡도가 높은 것이 단점입니다. 해시 충돌 시 체이닝으로 해결합니다.

int hash_find(int *dataset, int size, int target) {
    int max_val = dataset[0];
    int min_val = dataset[0];
    for(int i = 1; i < size; i++) {
        if(dataset[i] > max_val) max_val = dataset[i];
        if(dataset[i] < min_val) min_val = dataset[i];
    }
    
    int table_size = max_val - min_val + 1;
    int *hash_table = (int*)calloc(table_size, sizeof(int));
    
    for(int i = 0; i < size; i++) {
        hash_table[dataset[i] - min_val]++;
    }
    return hash_table[target - min_val];
}