순차 검색

<선형 검색>

직선 모양으로 늘어선 데이터 집합(배열, 링크드리스트) 에서 원하는 키 값을 갖는 요소를 만날 때 까지 앞부터 순서대로 요소를 검색하는 것을 선형 검색 또는 순차 검색 알고리즘이라고 한다. 

 

구체적인 과정을 아래의 데이터 나열을 예로 들어 살펴보겠습니다. 

이 배열에서 값 2의 요소를 선형 검색해보겠습니다.

6

4

3

2

1

3

6

4

3

2

1

3

6

4

3

2

1

3

6

4

3

2

1

3

(1) 첫번째 요소 6을 선택합니다. 원하는 값이 없습니다.

(2) 두번째 요소 4를 선택합니다. 원하는 값이 없습니다.

(3) 세번째 요소 3을 선택합니다. 원하는 값이 없습니다.

(4) 네번째 요소 2을 선택합니다. 원하는 값입니다. 검색 성공!!

→ 이경우는 검색에 성공한 경우입니다. 그런데 키 값과 같은 값을 가진 요소가 배열에 없을 수도 있습니다.

예를 들어 배열에서 5를 검색하면 검색을 끝까지 수행해도 키 값과 같은 값의 요소를 만나지 못했기 때문에 검색에 실패합니다.

 

위를 통해 선형 겁색의 종료 조건은 2개임을 알 수 있습니다. 다음 조건 중 하나라도 성립하면 검색을 종료합니다.

조건1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 → 검색 실패 (n+1회)

조건2. 검색할 값과 같은 요소를 발견한 경우 → 검색 성공 (n회)

배열의 요소수가 n개 일 때 조건 1,2를 판단하는 횟수는 평균 n/2회 입니다.

 

- 선형 검색의 시간 복잡도

최악의 경우 T(n) = n

최선의 경우 (찾고자 하는 값이 가장 처음에 위치한 경우 ) - 1회

 

선형 검색을 java를 이용하여 구현해보자

static int seqSearch(int[] a, int n, int key) {
    int i=0;
 
    while (true) {
        if(i==n)
            return -1;
        if(a[i] == key)
            return i;
        i++;
    }
}

 

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)라고 부른다.

원하는 키 값이 없을 경우 배열의 마지막에 키 값을 보초로 세워두어 선형검색의 종료조건 중 하나인 [검색할 값을 발견하지 못 하고 배열의 끝을 지나가는 경우]를 없애는 것이다. 

이렇게 종료 조건을 검사하는 비용을 반으로 줄이는 방법을 보초법이라고 한다.

 

(1) 2를 검색(검색 성공)

6

4

3

2

1

3

2 (보초)

 

(2) 5를 검색 (검색 실패)

6

4

3

2

1

3

5 (보초)

package Chapter03;
 
import java.util.*;
 
public class SeqSearchSen {
    static int seqSearchSen(int ar[], int s, int k) {
        ar[s] = k; //보초를 추가
        int i = 0;
        while (true) {
            if (ar[i] == ar[s])
                break;
            i++;
        }
        return i == s ? -1 : i;
    }
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("배열 길이 : ");
        int size = input.nextInt(); // 배열 길이
        System.out.print("찾을 키 값 : ");
        int key = input.nextInt(); // 찾을 키값
        int[] arNum = new int[size+1]; // 보초 저장을 위해 요솟수 size +1
        for (int i = 0; i < size; i++) {
            System.out.printf("arNum[%d] : ",i);
            arNum[i]= input.nextInt();
        }
        
        int index = seqSearchSen(arNum, size, key); // 찾는 키 있으면 인덱스 값, 없으면 -1
        if(index ==-1) {
            System.out.println("찾는 키 값이 없습니다.");
        }
        else{
            System.out.println("키 값이 존재하는 인덱스 : "+index);
        }
    }
}
 
    
 

 

이 프로그램은 종료 조건 1인 if(i==n) 이 필요하지 않기 때문에 하나의 if 문만 사용했습니다. 따라서 반복 종료에 대한 판단 횟수는 실제로 절반으로 줄어듭니다. 

while문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 하기 위해 삼항 연산자를 이용하여 변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환합니다.

 

 

---

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]