[자료구조] Chapter 06 탐색(순차 탐색,이진 탐색)

탐색 알고리즘의 개요

탐색은 무언가를 찾는다는 의미이다. 컴퓨터에서 무언가는 데이터로 정해져있으므로 컴퓨터의 탐색은 데이터를 찾는다는 의미를 가진다.

 

순차 탐색

순차 탐색은 처음부터 끝까지 모든 요소를 비교하며 원하는 데이터를 찾는 탐색 알고리즘이다. 순차 탐색은 한쪽 방향으로만 탐색할 수 있는 알고리즘이므로 선형탐색이라고 부르기도 한다.

순차 탐색은 처음부터 끝까지 모든 요소를 검사하는 전략이기에 성능이 좋지는 않다.

하지만 정렬되지 않은 데이터에서 원하는 항목을 찾을 수 있는 유일한 방법이며 버그를 일으킬 가능성이 적다는 장점이 있다.

 

순차 탐색보다 좋은 자기 구성법

• 마트 매장 입구에 진열된 특별 행사 상품
• MS 워드의 최근 문서 목록
• 배달 어플리케이션의 즐겨찾기

위의 예시들을 보면 자주 찾거나 사용하는 항목들을 우선적으로 배치하는 것을 알 수 있다.

자기 구성법은 이처럼 자주 사용되는 항목을 데이터 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법이다. 전진 이동법, 전위법, 빈도 계수법이 있다.

 

1) 전진 이동법

전진 이동법은 탐색된 항목을 데이터의 가장 앞(링크드 리스트의 헤드 부분)으로 옮기는 방법이다. 전진 이동법을 사용하면 한번 찾은 항목을 바로 찾을 때 한번에 찾을 수 있다.

하지만, 항상 특정 항목만 집중적으로 탐색되는 현상이 모든 데이터에서 발생하지는 않기 때문에, 한번 탐색된 항목이 다음에 또 다시 검색될 가능성이 높을 때 사용해야 한다.

Node* SLL_MoveToFront(Node** Head, int Target)
{
    Node* Current = (*Head);
    Node* Previous = NULL;
    Node* Match = NULL;
    
    while(Current != NULL)
    {
        if(Current -> Data == Target)
        {
            Match = Current;
            if(Previous != NULL)
            {
                // 자신의 이전 노드와 다음 노드를 연결하는 부분
                Previous -> NextNode = Current -> NextNode;
                
                // 자신을 리스트의 가장 앞으로 옮기기
                Current -> NextNode = (*Head);
                (*Head) = Current;
            }
            break;
        }
        else
        {
            Previous = Current;
            Current = Current -> NextNode;
        }
    }
    return Match;
}

 

 

2) 전위법

전위는 위치를 바꾼다는 의미이다. 순차 탐색에서 전위는 탐색된 항목을 바로 이전 항목과 바꾸는 알고리즘이다. 전진 이동법은 탐색된 항목을 무조건 앞으로 옮기지만, 전위법은 자주 탐색된 항목을 조금씩 앞으로 이동시킨다.

Node* SLL_MoveToFront(Node** Head, int Target)
{
    Node* Current = (*Head);
    Node* PPrevious = NULL;  // 이전 노드의 이전 노드
    Node* Previous = NULL;  // 이전 노드
    Node* Match = NULL;
    
    while(Current != NULL)
    {
        if(Current -> Data == Target)
        {
            Match = Current;
            if(Previous != NULL)
            {
                
                if(PPrevious != NULL)
                    PPrevious -> NextNode = Current;
                else
                    (*Head) = Current;
            
                Previous -> NextNode = Current -> NextNode;
                
                Current -> NextNode = Previous;
            }
            break;
        }
        else
        {
            if( Previous != NULL)
                PPrevious = Previous;
            
            Previous = Current;
            Current = Current -> NextNode;
        }
    }
    return Match;
}

 

 

3) 계수법

계수법은 데이터 내 각 요소가 탐색된 횟수를 별도의 공간에 저장해두고, 탐색된 횟수가 높은 순으로 데이터를 재구성하는 전략의 알고리즘이다. 하지만 이러한 계수법은 계수 결과를 저장하는 별도의 공간을 유지해야하고 계수 결과에 따라 데이터를 재배치해야 하기에 더 많은 시간과 자원이 소요된다는 단점이 있다.

 

 

이진 탐색

이진 탐색(Binary Search)은 정렬된 데이터에서 사용할 수 있는 고속 탐색 알고리즘이다.

위의 이미지에서 Binary Search를 보면 알 수 있듯, 탐색 범위를 1/2로 줄여나가는 방식이다.

*1,000개의 요소를 가진 데이터의 경우 최대 10번만 비교하면 어떤 요소든 찾을 수 있다.

 

과정은 아래와 같다.

• 데이터 중앙에 있는 요소를 고른다. (위의 이미지에서는 5이다.)
• 중앙 요소값과 찾고자하는 목표 값을 비교한다. (위의 이미지에서는 9이다.)
• 목푯값이 중앙 요솟값보다 작다면 중앙을 기준으로 왼편에 대해, 크다면 오른편에 대해 이진 탐색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

 

1) 이진 탐색의 성능 측정

이진 탐색은 처음 탐색을 시도할 때 탐색 대상의 범위가 1/2로 줄어든다. 다음 시도에서는 원래의 반의 반, 그 다음 시도에서는 1/16으로 탐색 대상의 범위가 줄어든다.

2) 이진 탐색의 구현

ElementType BinarySearch(Score ScoreList[], int Size, ElementType Target)
{
    int Left, Right, Mid;
    
    Left = 0;
    Right = Size-1;
    
    while(Left <= Right)  // 탐색 범위의 크기가 0이 될 때까지 while문을 반복한다.
    {
        Mid = (Left + Right) / 2;   // 중앙 요소의 위치를 계산한다.
         
        if(Target == ScoreList[Mid].score)   // 중앙 요소가 담고있는 값과 목표값이 일치하면 반환한다.
            return &(ScoreList[Mid]);
        else if(Target > ScoreList[Mid].score)
            Left = Mid + 1;
        else
            Right = Mid - 1;
    }
    return NULL;
}

 

3) C언어 표준 라이브러리의 이진 탐색 함수: bsearch()

C언에 표준 라이브러리에 퀵 정렬을 구현한 sort() 함수가 있는 것 철험 이진 탐색을 구현한 bsearch() 함수도 있다.

void *bsearch(
    const void *key,
    const void *base,
    size_t num,
    size_t width,
    int (_ _cdecl *compare)(const void *, const void*)
);

첫번째 매개변수인 key는 찾고자 하는 목표값 데이터의 주소이다.

두번째 매개변수인 base는 데이터 배열의 주소를 가리키는 포인터이고, 세번째 매개변수인 num은 그 데이터 요소의 개수. 즉 데이터의 크기이다. 네번째 매개 변수 width는 데이터 요소 하나의 크기이며, 마지막 매개 변수는 비교를 수행한 결과를 반환하는 함수에 관한 포인터이다.