[C] 탐색 알고리즘 (선형 탐색, 이진 탐색)

탐색 알고리즘(Search Algorithm)
자료구조 안에 저장되어 있는 특정 자료를 찾아오는 알고리즘이다
대표적인 탐색 알고리즘으로는
선형 탐색, 이진 탐색, 해시 기반 탐색이 있다

선형 탐색(Linear Search)
자료구조의 모든 자료를 순서대로 훑어가며 특정 자료를 찾는 알고리즘이다

예를 들어 반복문을 돌면서 순회하면서 찾는 경우를 의미한다

 

이진 탐색(Binary Search)
정렬되어 있는 자료구조에 절반씩 자료를 제거해 가며 원하는 자료를 찾는 알고리즘이다
단계가 진행 될 때마다 탐색 범위가 절반씩 줄어들어서 이진 탐색이라고 부른다

 

 

선형탐색 vs. 정렬 후 이진탐색
선형탐색과 이진탐색의 공간 복잡도는 같지만,

시간 복잡도는 이진탐색이 O(N) 보다 빠를 수 있다

따라서,

탐색 빈도가 높다면, 정렬 후 이진탐색

탐색 빈도가 낮고 배열의 삽입이나 삭제가 적다면, 정렬 후 이진탐색

탐색 빈도가 낮고 배열의 삽입이나 삭제가 많다면, 선형 탐색

 

선형탐색 vs. 해시탐색

	선형탐색	해시탐색
용이성	모든 자료구조 가능	모든 자료구조 가능
시간 복잡도	O(N)	O(1)
공간 복잡도	O(N)	O(N) 보다 큰 공간 복잡도

 

 

이진탐색 구현 코드

#include <stdio.h>

enum
{
    LENGTH = 1024,
    INVALID = -1,
};

int BinarySearch(int InData[], int InLength, int InKey);

int main(void)
{
    int Data[LENGTH + 1];
    int i = 0;

    for (i = 0; i < LENGTH; ++i)
    {
        Data[i] = i * 2;
    }

    int FoundIndex = BinarySearch(Data, LENGTH, 512);
    if (FoundIndex != INVALID)
    {
        printf("Data[%d] = %d\n", FoundIndex, Data[FoundIndex]);
    }

    FoundIndex = BinarySearch(Data, LENGTH, 511);
    if (FoundIndex != INVALID)
    {
        printf("Data[%d] = %d\n", FoundIndex, Data[FoundIndex]);
    }

    return 0;
}

int BinarySearch(int InData[], int InLength, int InKey)
{
    int Left, Mid, Right;
    Left = 0;
    Right = InLength - 1;

    while (Left <= Right)
    {
        Mid = (Left + Right) / 2;

        if (InKey < InData[Mid])
        {
            Right = Mid - 1;
        }
        else if (InKey == InData[Mid])
        {
            return Mid;
        }
        else if (InData[Mid] < InKey)
        {
            Left = Mid + 1;
        }
    }

    return INVALID;
}