순차 검색(Sequential Search) 또는 선형 검색(Linear Search) 알고리즘

순차 검색(Sequential Search) 알고리즘이란?

주어진 데이터를 처음부터 검색하는 알고리즘.

무작위로 늘어놓은 데이터 모임에서 검색을 수행할 때 유효.

 

순차 검색 종료조건

• 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
• 검색할 값과 같은 요소를 발견한 경우

자바로 구현하기

//요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색한다.
static int seqSearch(int[] a, int n, int key) {
    for(int i=0; i<n; i++) {
        if(a[i] == key) {
            return i;
        }
    }
    return -1;
}

 

보초법(sentinel method)

순차 검색은 반복할 때 마다 종료 조건 2개를 모두 판단한다.

이 판단 비용을 50% 절약하는 방법이 보초법이다.

검색을 실행하기 전에 먼저 검색하고자 하는 키 값을 맨 끝 요소에 저장한다. 이 때 저장하는 값을 보초(sentinel)라고 한다.

이 방법을 쓰면 원하는 값이 원래 데이터에 없어도 검색 성공 종료 조건이 발생해서 검색을 종료시킬 수 있기 때문에

검색 실패 종료조건은 검색하지 않아도 된다.