자료구조 - 선형 검색(linear search), 순차 검색(sequential search)

선형 검색

 

 

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

 

 

요솟수가 7개 이고 [ 6, 4, 3, 2, 1, 3, 0 ] 으로 되어 있고 검색을 2로 할 때입니다.

 

import java.util.Scanner;

public class SeqSearch {

    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++;
        }
    }

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

        System.out.println("요솟수 : ");
        int num = sc.nextInt();

        int[] x = new int[num];

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

        System.out.println("검색할 값");
        int key = sc.nextInt();

        int idx = seqSearch(x, num, key);

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

    }

}

 

 

 

 

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

 

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

 

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

 

④ 네 번째 요소 2를 선택합니다. 원하는 값입니다. 검색 성공!

 

 

 

그런데, 키 값과 같은 값을 가진 요소가 배열에 없을 수 도 있습니다.

찾지 못하면 -1를 리턴하여 찾지 못하였다고 콘솔에 나타냅니다.

 

 

이때, 배열의 검색을 while문이 아니라 for문으로 구현하면 프로그램은 보다 짧고 간결해집니다.

 

 

import java.util.Scanner;

public class SeqSearch {

    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 sc = new Scanner(System.in);

        System.out.println("요솟수 : ");
        int num = sc.nextInt();

        int[] x = new int[num];

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

        System.out.println("검색할 값");
        int key = sc.nextInt();

        int idx = seqSearch(x, num, key);

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

    }

}

 

 

보초법

 

 

선형검색은 반복할 떄마다 결과를 찾았는지, 못찾았는지를 모두 판단합니다. 단순한 판단이라고 생각할 수 있지만 종료 조건을 검사하는 비용은 결코 무시할 수 없습니다.

 

이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel method)입니다.

 

배열 요소 a[0] ~ a[6]은 초기에 준비해 놓은 데이터입니다. 검색하지 전에 검색하고자 하는 키 값을 맨 끝 요소 a[7]에 저장합니다. 이때 저장한느 값을 보초(sentinel)라고 합니다.

 

원래의 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 찾지 못했을 때를 판단하는 조건이 성립합니다.

이렇게 하면 원하는 키 값을 찾지 못했을 때를 판단하는 배열의 끝을 지나쳤을 때 조건이 없어도 됩니다.

보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역활을 합니다.

 

import java.util.Scanner;

public class SeqSearchSen {

    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 sc = new Scanner(System.in);

        System.out.println("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num + 1];

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

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

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

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

}