ING

* 선형 검색(순차검색)이란?

   배열 검색 중 가장 기본적인 알고리즘으로 요소가 직선 모양으로 늘어선 배열에서 원하는 키값을 찾을 때까지

   맨 앞부터 순서대로 요소를 검색하는 것

위의 표와 같이 배열이 존재할 경우 1을 찾기 위해 0, 1, 2, 3번째 배열을 모두 검색하는 방법이다.

선형검색을 하게되면 종료의 조건은 아래 두가지로 정의 할 수 있다.

   1) 검색값을 찾은 경우

   2) 검색값이 존재하지 않는 경우

이때 종료 판단 횟수를 줄이는 역할을 하게 되는 것이 보초법 이다.

* 보초란?

   검색하고자 하는 키 값을 맨 끝 요소에 저장하는 값이다. 

   일반배열에서 7이라는 값을 찾으려고 할때 아래와 같이 배열이 구성 된다.

    - 보초 넣은 배열

따라서 보초는 반복문에서 종료 판단 중 2)검색값이 존재하지 않는 경우를 체크하지 않아도 되게 함으로써 종료 판단을 2회에서 1회로 줄이는 역할을 한다.

아래는 보초법를 사용한 알고리즘 책의 p106 실습 3-3 예제입니다!

package chap03;

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 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+"]에 있습니다.");
        }
    }
}

* 보충수업 3-1 무한루프

   do while문은 끝까지 읽어야만 무한 루프인지 알기 때문에 권장하지 않는다!