보초법 sentinel method

선형검색의 종료조건 두 가지를 검색을 반복할 때 마다 판단하는 것을 효율적으로 줄이기 위한 개선방법.

검색하고자 하는 키 값을 기존 배열의 맨 끝 자리에 추가로 저장하고 이를 보초(sentinel)라고 부른다. 이는 검색할 때

원하는 키 값이 없을 경우 배열의 마지막에 키 값을 보초로 세워두어 선형검색의 종료조건 중 하나인 [검색할 값을 발견하지 못 하고 배열의 끝을 지나가는 경우]를 없애는 것이다. 

 

따라서 보초법을 사용하게 되면 반복문의 종료 판단 횟수를 2회에서 1회로 줄인다.

 

public class SeqSearchSen {

	static int seqSearchSen(int[] a, int n, int key){
		int i = 0;
		
		a[n] = key;							//보초를 추가
        
		//배열 요소를 순서대로 검색, 보초가 있기 때문에 if는 하나의 조건만 필요
		while (true){
			if (a[i]== key)				
				break;
			i++;
		}
        //변수 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+"]에 있습니다.");
	}