배열 검색 (선형검색, 보초법)

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 값을 찾을때까지 맨 앞부터 순서대로 요소를 검색하면 된다.

이것을 선형검색(linear search)또는 순차검색(sequential search)이라고 한다.

그리고 배열을 이용해 선형검색을 수행하는 코드는 다음과 같다.

import java.util.*;

public class Main {
    //배열의 길이가 n인 배열 a에서 key라는 값을 검색하여 존재하면 인덱스 i를, 존재하지않으면 -1을 반환한다.
    static int seqSearch(int[] a, int n, int key){
        for (int i = 0; i < n; i++) {
            if(a[i]==key)
                return i; //검색성공
        }
        return -1; //검색실패
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("배열의 길이: ");
        int num = scanner.nextInt();
        int[] x = new int[num];

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

        System.out.print("검색할 값: ");
        int key = scanner.nextInt();

        int idx = seqSearch(x, num, key);
        if(idx==-1)
            System.out.println("해당값이 배열에 없습니다.");
        else
            System.out.println(key+"는 x["+idx+"]에 있습니다.");
    }
}

그런데 위의 예에서는 배열의 모든 인덱스를 순회해야만 하므로 검사비용이 크다.

 

1. key값을 발견하지 못하고 배열의 끝을 지나갔는지. (검색 실패조건)

2. key값을 발견했는지. (검색 성공조건)

매 반복마다 이 두가지의 종료조건을 모두 판단하기 때문이다.

 

이 비용을 반으로 줄이는 방법이 보초법이다. (sentinal method)

검색을 수행하기 전에 검색하고자하는 값을 배열의 맨 끝에 저장하고, 이 값을 보초라고 한다.

이렇게 보초를 배열의 끝에 추가하게되면, key값을 못찾는 경우의 수가 사라지므로

두가지의 종료조건 중 2번(key를 발견했는지)만 수행하면 된다.

import java.util.*;

public class Main {
    //배열의 길이가 n인 배열 a에서 key라는 값을 검색하여 존재하면 인덱스 i를, 존재하지않으면 -1을 반환한다.
    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 scanner = new Scanner(System.in);
        System.out.print("배열의 길이: ");
        int num = scanner.nextInt();
        int[] x = new int[num+1]; //보초가 추가됐으니 배열길이 +1

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

        System.out.print("검색할 값: ");
        int key = scanner.nextInt();

        int idx = seqSearchSen(x, num, key);
        if(idx==-1)
            System.out.println("해당값이 배열에 없습니다.");
        else
            System.out.println(key+"는 x["+idx+"]에 있습니다.");
    }
}