[Algorithm] 보초법

선형검색은 반복할 때마다 종료 조건 2가지 (검색 값 발견할 경우, 못 할 경우)를 모두 판단하는데 이 검사 비용을 반으로 줄이는 방법이 보초법입니다. 

 

검색하기 전에 검색하고자 하는 키 값을 맨 끝 인덱스에 저장합니다. 이때 저장하는 값을 보초(sentinel)라고 합니다.

 

이렇게 하면 찾는 값이 배열에  존재하지 않아도 맨 끝 인덱스까지 검색하면 종료 조건이 성립합니다.(찾으려는 값과 같은 요소 발견, 단, 발견한 것은 보초) 또한 원하는 키 값을 찾지 못한 종료조건까지도 성립할 수 있습니다.

 

그렇기 때문에 반복문의 종료 판단 횟수를 2회에서 1회로 줄여줍니다.

 

//선형검색 - 보초법
public class SeqSearchSen {
    //요소수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색합니다.
    static int seqSearchSen(int[] a, int n, int key){
        int i = 0;

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

        System.out.println("* 보초가 들어간 배열 *");
        for (int j = 0; j <= n; j++) {
            System.out.println("X["+j+"] ="+a[j] );
        }
        System.out.println();
        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 num = sc.nextInt();
        int[] x = new int[num + 1];

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

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

        int idx = seqSearchSen(x, num, ky);

        if(idx == -1) System.out.println("없습니다");
        else System.out.println(ky+"는 "+"x["+idx+"]에 있습니다.");
    }
}

 

실행결과

요소수 : 3
x[0] : 1
x[1] : 2
x[2] : 3
검색할 값 : 4
* 보초가 들어간 배열 *
X[0] =1
X[1] =2
X[2] =3
X[3] =4

없습니다