[자료구조와 알고리즘] 2. 보초법

 * 1) 선형검색의 한계  선형검색은 무한루프를 통해 검사를 진행하므로 종료조건에 있어 비용이 든다.
 *  검색 실패, 검색 실패, 검색실패, 검색 성공 과 같은 식이다. 
 *  => 이 비용을 반으로 줄이는 방법이 보초법이다. 

 * 1) 2를 검색해서 성공하는 조건 2 5 3 4 [2]
 * 2) 5를 검색해서 실패하는 조건 0 2 4 1 [5]
 * 이와 같이 끝자리 수에 검색하고자 하는 값을 보초라고하는데, 원하는 값이 존재하지 않아도 보초값까지 검색하면 종료가 성립된다. 

 * 다시 말해 
 * #선형 검색 의 경우 : 
 *  int i = 0 으로 요솟수를 정의하고 
 *  while(true) {
 *  if(i==n)
 *  return -1; 
 *  if(a[i] == key)
 *  return 1; 
 * 과같이 첫번째 if문처럼 종료조건1을 달아야하는데, 이 과정이 필요가 없어지는 것이다. 
 * 따라서 보초는 반복문에서 종료 판단횟수를 2회에서 1회로 줄이는 역할을 한다. 

package chapter1;

import java.util.Scanner;

public class SeqSearchSen {


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

			a[n] = key;					// 보초를 추가 (a[요솟수] 니까 끝자리에 , 검색값을 한번 더 배치시킨다. 이것은 보초값을 가장 끝자리에 자리시키는 행위 

			while (true) {
				if (a[i] == key)		// 검색 성공!
					break;
				i++;
			}
			/*
			for(i=0; i<n; i++) {
				if(a[i] == key)
						break; 
			}*/
			
			// while이 반복되면, 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 한다. 
			// 변수 i 값이 n 이면 찾은 값이 보초값이므로 검색실패를 나타내는 -1을 반환한다. 
			
			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 + "]에 있습니다.");
		}
}