(1) 순차 탐색

1. 탐색(Searching) 알고리즘

만일 여러분이 명함을 차곡차곡 받아서 모아두었다고 하자. 혹은 친구들의 전화번호를 수
첩에 적어두었다고 하자. 그런데 어느날 누군가에게 전화를 걸어야 할 일이 생겼다. 여러분
은 전화번호를 찾기 위해 명함을 혹은 수첩의 전화번호를 뒤져야 한다. 그러면 어떤 방식으
로 원하는 전화번호를 찾아낼 것인가?

(1) 순차 탐색

이 같은 문제를 해결하는 가장 간단한 방법은 역시 '순차탐색(Sequential Searching혹은
Linear Searching)'일 것이다. 순차탐색의 원리는 아주 일상적인 것으로 간단히 얘기하자면
앞에서부터 차근차근 하나씩 찾아나가는 것을 얘기한다. (그림1 참조)

앞에서 얘기한 명함 검색의 예로 살펴봄면 프로그램은 다음과 같이 될 것이다.

시작
        While 명함이 남아있음 and 현재 원하는 명함이 아님)
                다음 명함
        If (명함이 있음)
                명함을 반환
        Else
                명함이 없음을 반환
끝

위의 알고리즘을 C언어를 사용하여 하나의 함수로 구현하다면 다음과 같은 형식이 된다.
아래의 예에서는 검색의 대상이 되는 자료가 정수형이고, 배열이 a에 저장되어 있으며
NOT-EXIST는 미리 정의된 것으로 가정하였다. 그리고, last-item은 배열의 마지막을 표시하
는 정수다. 이후의 검색의 예에서도 이와 같은 가정에 근거한다.

(리스트1) 순차 탐색 알고리즘의 구현 예
int Linear_Search(int key,int *a,int last_item)
{
int curr_item;

        curr_item=0;
        While ((curr_item<=last_item) && (a[curr_item] != key))
                curr_item++;
        if (curr_item<=last_item)
                return curr_item;
        else
                return NOT_EXIST;
}

이와 같은 순차탐색의 수행 속도를 약간 향상시키는 방법으로 '보초(sentinel)'를 세우는 방
법이 있다. 이 방법을 사용하면 루핑에서 현재 항목이 마지막 항목인지에 대한 검사를 할
필요가 없으므로 검색 속도를 향상시킬 수가 있다. 구체적인 구현 방법은 배열의 마지막 항
목의 다음에 찾고자 하는 값을 미리 넣어 둠으로써 원하는 항목이 없는 경우에도 루핑을 빠
져 나올 수 있도록 한 것이다. 이와 같이 배열의 마지막을 지키는 값을 '보초'라고 부른다(그
림2 참조).

(리스트 2) 보초를 사용하는 개량된 순차 탐색 알고리즘
int Advanced_Linear_Search(int key,int *a,int last_item)
{
        int curr_item;
        curr_item=0;
        a[n+1]=key;
        While (a[curr_item] != key)
                curr_item++;
        if (curr_item<=last_item)
                return curr_item;
        else
                return NOT_EXIST;
}

이와 같이 보초를 사용하는 방법은 다른 많은 경우에 응용될 수 있으므로 기억해 두면 좋다.
단, 이 방법을 사용할 경우에 보초를 위한 메모리를 미리 할당하는 것에 주의하여야 한다.