검색 알고리즘 - 선형 검색

오늘은 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘 중에 선형 검색에 대해 알아보자.

📘 선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이때 이것을 선형 검색(linear search) 또는 순차 검색(sequential search)이라고 하는 알고리즘이다.

✏ 선형 검색의 종료 조건

선형 검색의 종료 조건은 2가지이다.

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

'조건 ❶' 은 검색 실패, '조건❷'는 검색 성공일 때의 상황이다.

✏ 선형 검색 코드

간단한 코드로 선형 검색의 예를 살펴보자. 선형 검색의 시간 복잡도는 평균적으로 O(n)이다.

import java.util.Scanner;

public class Main {
    static int search(int[] a, int n, int key) {
        int i = 0;

        while (true) {
            if (i == n)           // 검색 실패 (-1을 반환)
                return -1;
            if (a[i] == key)      // 검색 성공 (인덱스를 반환)
                return i;
            i++;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("검색하는 배열의 크기 : ");
        int len = sc.nextInt();
        int[] x = new int[len];

        for (int i = 0; i < len; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = sc.nextInt();
        }

        System.out.print("검색할 값 : ");
        int key = sc.nextInt();
        int idx = search(x, len, key);

        if (idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(key + "값은 x[" + idx + "]에 있습니다.");
    }
}

위의 코드를 실행하면

이러한 결과가 나온다.

search 메서드는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환하는 메서드이다. 또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다. 값이 key인 요소가 존재하지 않을 경우엔 -1을 반환한다.

배열 검색 시 요소의 인덱스를 가르키는 건 변수 i이다. i는 0으로 초기화하고 요소 하나를 검색할 때마다 while문이 제어하는 루프 본문의 끝에서 증가시킨다. while문을 빠져나가는 경우에는 검색에 성공하거나 실패했을때 둘 중의 하나의 경우가 성립한 경우이다.

search 메서드에서 while문 대신 for문으로 구현하면 보다 짧고 간결해진다.

for (int i = 0; i < n; i++)
	if (a[i] == key)
    	return i;
return -1;

📘 보초법

선형 검색은 종료 조건 1과 2를 모두 판단하기 때문에 검사 비용이 많이든다고 볼 수 있다.
원하는 key값을 찾지 못하는 경우에 관한 종료조건을 제거함으로써 종료 판단 횟수를 1로 줄이는 방법이 보초법이다.

보초법을 사용하는 방법은 검색하기 전에 검색하고자 하는 키 값을 검색하려고 하는 배열의 맨 끝에 추가하여 저장한다. 이때 저장하는 값을 보초(sentinel)라고 한다.
이렇게 하면 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 맨 끝 요소까지 검색하면 종료가 된다. 이렇게 하면 원한느 키 값을 찾지 못했을 때를 판단하는 조건이 없어도 되는 것이다.
보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 하기에 보다 효율적이다.

✏ 선형 검색 - 보초법 코드

import java.util.Scanner;

public class Main {
    static int search(int[] a, int n, int key) {
        int i = 0;

        a[n] = key;         // 보초를 추가

        while (true) {
            if (a[i] == key)
                break;
            i++;
        }
        return i == n ? -1 : i;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("검색하는 배열의 크기 : ");
        int len = sc.nextInt();
        int[] x = new int[len + 1];     // 요솟수 = 원래 배열의 크기 + 보초

        for (int i = 0; i < len; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = sc.nextInt();
        }

        System.out.print("검색할 키의 값 : ");
        int key = sc.nextInt();
        int idx = search(x, len, key);

        if (idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(key + "값은 x[" + idx + "]에 있습니다.");
    }
}

검색할 값 key를 보초로 a[n]에 대입한다.

배열 요소를 순서대로 검사하지만 이번엔 종료 조건이 한개이기 때문에 while문 속에 if문이 1개만 존재한다.

while문의 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 보초인지 판단해야 한다. 변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.