[알고리즘] Linear Search

[Algorithm - Linear Search]

 

 

※ 검색 알고리즘

- 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 살펴보자.

 

 

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

 

 

- 선형 검색(순차 검색)은 결과가 두 조건으로 나누어짐

 

 

 

- 배열의 요소를 맨 앞부터 순서대로 검색함

 

- key 값인 14를 맨 앞부터 찾는다면 4번째 인덱스에서 key 값을 찾게 되고 검색 성공

 

 

 

 

- key 값인 99를 맨 알부터 찾는다면 배열을 순차적으로 검색해도 값이 없기 때문에 검색 실패 

 

 

※ 선형 검색 구현 (java)

package chap03.practice;

import java.util.Scanner;

/**
* 선형 검색
*/
class SeqSearchFor {

// 배열 a의 앞쪽 n개의 요소에서 key와 같은 요소를 선형 검색
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 stdIn = new Scanner(System.in);

System.out.print("요솟수: ");
int num = stdIn.nextInt();
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 ky = stdIn.nextInt();
int idx = seqSearch(x, num, ky);

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

- 배열 검색의 종료 조건은 2개임을 알 수 있다.

 

- 조건 1: 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

- 조건 2: 검색할 값과 같은 요소를 발견한 경우

 

- i == n 이 성립하는 경우 (종료조건 1 : 검색 실패이므로 -1을 반환)

- a[i] == key가 성립하는 경우 (종료조건 2: 검색 성공이므로 i를 반환)

 

 

 

※ 보초법

 

- 선형 검색은 반복할 때마다 종료 조건 1과 2를 모두 판단한다. 단순한 판단이라고 생각할 수 있지만 종료 조건을 검사하는 비용은 결코 무시할 수 없다.
- 종료 조건 1.  검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우- 종료 조건 2. 검색할 값과 같은 요소를 발견한 경우
- 이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel method) 이다.- 검색하기 전에 검색하고 하는 키 값을 맨 끝 요소 a[n+1]에 저장한다. 이때 저장하는 값을 보초라고 한다. 
- 그러면 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 a[n+1]까지 검색하면 종료조건 2가 성립한다.- 이렇게 하면 원하는 키 값을 찾지 못했을 때를 판단하는 종료조건 1이 없어도 된다.
- 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

 

※ 보초법 구현 

package chap03.practice;

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(ky + "은(는) x[" + idx + "]에 있습니다.");
    }
}