[Java] 검색 - 선형(순차)검색 / 보초법

본 포스팅은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 Java편'을 스터디 한 내용입니다.

 

선형 검색

원하는 키(key)값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 요소를 검색하는 것을 선형(linear) 또는 순차(sequential) 알고리즘 이라고 함

 

검색의 종료 조건

① 검색할 값과 같은 요소를 발견한 경우 (n 회, 평균 n/2회)

② 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(n+1회)

그림1. 검색할 값과 같은 요소를 발견한 경우(24 검색)

그림2. 검색할 요소를 발견하지 못한 경우(85 검색)

 

선형검색 구현 코드

n개의 요소를 대상으로 값이 key인 요소를 선형검색하고 검색한 요소의 index를 반환함.

값이 key인 값이 여러개 존재할 경우, 최초 발견된 index만 반환하고 검색이 종료됨.

import java.util.Scanner;

/**
 * @Date 2020. 1. 27.
 * @Time 오후 1:02:36
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class seqSearch {

	
	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : sequenceSearhc
	 * @return : int
	 */
	static int sequenceSearhc(int [] a, int num, int key) {
		
		int i=0;
		
		for(i=0; i<num; i++) {			
			if(a[i] == key) {				
				return i;				
			}			
		}
		
		return -1;
		
	}
	
	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : main
	 * @return : void
	 */
	public static void main(String[] args) {
		
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("요솟수 : ");
		int num = stdIn.nextInt();
		int[] searchArray = new int[num];
		
		for(int i=0; i<searchArray.length; i++) {
			
			System.out.println("searchArray["+i+"] : ");
			searchArray[i] = stdIn.nextInt();
			
		}
		
		System.out.println("검색하고자 하는 값 : ");
		int key = stdIn.nextInt();
		
		int flag = sequenceSearhc(searchArray, num, key);
		
		if(flag == -1) {
			
			System.out.println("검색결과가 없습니다.");
			
		}else {
			
			System.out.println("검색결과는 "+searchArray[flag]+"이고, index는"+flag+"입니다.");
			
		}

	}

}

 

보초법 (Sentinel Method)

선형검색은 종료조건 1과 2를 모두 판단하기 때문에 검사 비용이 많이든다고 볼 수 있음.

원하는 key값을 찾지못하는 경우에 관한 종료조건을 제거함으로써 종료 판단횟수를 1로 줄이는 방법이 보초법임.

 

- 검색 전, 검색하고자 하는 key 값을 배열의 맨 끝 요소에 저장

- 검색 결과, key 값이 원래 data에 존재하지 않아도 검색결과가 없는 경우에 관한 종료조건이 필요없음

그림3. 보초법

보초법 구현 코드

검색하고자하는 key값을 sentinelSequenceSearch 메소드에서 배열의 맨 끝에 삽입한 후, key값과 배열의 요소를 for문을 활용해 비교하면서 index값을 return 시킴. 따라서, 종료 판단횟수는 1회로 비용 절감이 가능함.

import java.util.Scanner;

/**
 * @Date 2020. 1. 27.
 * @Time 오후 1:14:26
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class sentinelSeqSearch {

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : sentinelSequenceSearch
	 * @return : int
	 * @Description : 보초법을 활용한, 선형검색 메소드
	 */
	static int sentinelSequenceSearch(int [] sentinelArray, int num, int key) {
		
		sentinelArray[num] = key; //배열의 맨 마지막 값에 key대입
		int searchResult = 0;
		
		for(int i=0; i<sentinelArray.length; i++) {
			
			if(sentinelArray[i] == key) {
				
				searchResult = i;
				break;
				
			}
			
		}
		
		return searchResult;
		
	}

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : main
	 * @return : void
	 * @Description : 실행을 위한 main method
	 */
	public static void main(String[] args) {

		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("요솟수 : ");
		int num = stdIn.nextInt();
		int [] sentinelArray = new int[num+1];
		
		for(int i=0; i<num; i++) {
		
			System.out.println("sentinelArray["+i+"] : ");
			sentinelArray[i] = stdIn.nextInt();
			
		}
		
		System.out.println("검색할 값 : ");
		int key = stdIn.nextInt();
		int searchResult = sentinelSequenceSearch(sentinelArray, num, key);//검색결과
		
		if(searchResult == num) {
			
			System.out.println("검색결과가 없습니다.");
			
		}else {
			
			System.out.println("검색결과는 "+sentinelArray[searchResult]+"이고, 배열의 index는 "+searchResult+"입니다.");
			
		}

	}

}

 

참고 : 무한루프의 구현

for문, while문은 무한루프 여부를 코드의 첫 줄에서 바로 확인 가능하지만, do ~ while 구문은 마지막에 확인 가능하므로 do ~ while구문은 무한루프에서 사용하지 않는 것이 좋음