[Java] 선형 검색 Linear Search

선형 검색

선형 검색 (=순차 검색)은 배열에서 검색할 값을 처음부터 순서대로 하나하나씩 비교하여 찾는 방식이다. 예를 들어 배열 {1, 2, 3, 4, 5}에서 값 3을 선형 검색으로 찾는다면, 첫 값인 1과 3을 비교, 다음 값인 2와 3을 비교, 그리고 다음 3과 3을 비교해서 찾게 된다.

 

 

Java로 선형 검색 구현

일반적으로 선형 검색을 할 경우, 다음 두 가지 결과가 발생한다.

1. 배열을 끝까지 탐색했음에도 불구하고 검색할 값을 찾지 못함 -> 검색 실패
2. 배열 탐색 중 검색할 값을 찾음 -> 검색 성공

이를 메소드로 구현하면 다음과 같다.

import java.util.Scanner;

class SeqSearch {
    // 크기가 n인 자바 배열 a에서 key와 값이 같은 요소를 선형 검색하는 메소드
    static int seqSearch(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 stdIn = new Scanner(System.in);

        System.out.print("배열 크기: ");
        int num = stdIn.nextInt();
        // 크기가 num인 배열
        int[] x = new int[num];

		// 배열의 요소들을 입력받음
        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }

        // 검색할 키값을 입력받음
        System.out.print("검색할 값: ");
        int key = stdIn.nextInt();
        
        stdIn.close();
        
        // 배열 x에서 값이 key인 요소를 검색
        int idx = seqSearch(x, num, key);

        if (idx == -1)
            System.out.println("검색 값이 배열에 없습니다.");
        else
            System.out.println("검색 값은 x[" + idx + "]에 있습니다.");
    }
}

 

선형 검색을 구현한 seqSearch메소드는 i가 증가할 때마다 두 가지 판단을 하기 위해 if문이 두 개 가지고 있다.

1. 검색 실패를 판단. i == n 이면 끝까지 검색했는데 찾지 못했다는 것을 의미한다.
2. 검색 성공을 판단. a[i] == key이면 인덱스 i에서 원하는 값을 찾았다는 것을 의미한다.

 

보초법 Sentinel Method

앞서 구현된 선형 검색 메소드에서 매번 두 개의 판단을 하는 것이 성능상 비효율적이기에, 하나의 판단을 줄인 방법인 보초법이 있다. 보초법은 입력받은 배열의 끝에 검색할 값을 요소로 추가하여 1번 조건 판단을 없애는 방식이다. 예를 들어,

 

{1, 2, 3} 배열에서 값 8을 검색하는 경우, 배열 끝에 8을 추가하여

{1, 2, 3, 8} 배열을 만들어서 여기서 8을 검색하게 된다.

 

이러면 검색할 값이 반드시 배열에 들어가므로 매번 검색 실패를 판단이 불필요하고 검색 성공만이 존재하게 된다. 검색값이 배열의 몇 번째 인덱스에 있었는지 반환받아, 마지막 인덱스에 존재하였다면 본래 배열에 검색값이 없었다는 판단이 가능해진다.

이를 구현하면 다음과 같다.

import java.util.Scanner;

class SeqSearchSen {
    //--- 요솟수가 n인 배열 a에서 key와 값이 같은 요소를 보초법으로 선형 검색 ---//
    static int seqSearchSen(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 stdIn = new Scanner(System.in);

        System.out.print("요솟수 : ");
        int num = stdIn.nextInt();
        int[] x = new int[num + 1];                        // 요솟수가 num + 1인 배열

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

        System.out.print("검색 값 : ");                    // 키값을 읽력받음
        int ky = stdIn.nextInt();

        int idx = seqSearchSen(x, num, ky);              // 배열 x에서 값이 ky인 요소를 검색

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

 

앞서 구현한 선형 검색에 비해 매번 하나의 if문만 판단하므로 성능이 더 좋아진다. 반면 마지막에 i == n ? -1 : i 라는 판단이 추가로 필요한데, 여기서 i == n 이라면 본래 배열에서 값을 찾지 못하고 보초로 추가한 값까지 i가 도달했다는 뜻이기에 검색이 실패했고, -1을 반환하는 코드이다.