[JAVA] 선형 검색(Linear Search), 보초법(Sentinel Method)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

선형 검색(순차 검색)

선형 검색은 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 것을 말한다.

 

선형 검색에서 검색의 종료 조건은 아래의 2개와 같다.

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

 

첫 번째 조건이 성립하면 검색 실패, 두 번째 조건이 성립하면 검색 성공이다.

배열의 요솟수가 n개이면 조건 1, 2를 판단하는 횟수는 평균 n/2회이다.

public class Main{
	static int seqSearch(int[] arr, int key)
	{
		for(int i = 0; i < arr.length; ++i) {
			if(arr[i] == key) return i;
		}
		return -1;
	}
	
	public static void main(String[] args) {
		int[] arr = {22,8,55,32,120,55,70};
		System.out.println("key의 인덱스는 " + seqSearch(arr, 55) + " 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)");
	}
}
/*
key의 인덱스는 2 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)
*/

값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다.(55를 검색하면 arr[2]와 arr[5]의 두 곳에 존재하지만 가장 먼저 찾음 arr[2]의 인덱스 값인 2를 반환한다.)

 

key와 일치하는 모든 요소의 수 리턴

배열의 원소 개수가 n인 배열에서 key와 일치하는 모든 원소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치한 원소의 수를 리턴하는 메소드를 작성

( 예를 들어 배열의 원소가 {1,9,2,9,4,6,7,9}이고 key가 9면 배열 idx에 {1,3,7}을 저장하고 3을 리턴)

static int searchIdx(int[] arr, int key) //while문으로 구현
{
    int []idx = new int[arr.length];
    int count = 0;
    for(int i = 0; i < arr.length; ++i)
    {
        if(key == arr[i]) idx[count++] = i;
    }
    return count;
}

 

실행 예제

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.print("입력할 데이터의 개수 입력 : ");
    int num = sc.nextInt();
    int []arr = new int[num];
    for(int i = 0; i < arr.length; ++i)
    {
        System.out.print("데이터 입력 : ");
        arr[i] = sc.nextInt();
    }
    System.out.print("찾을 데이터 입력 : ");
    num = sc.nextInt();
    System.out.println("key는 " + searchIdx(arr, num) + "개 있습니다.");
}
/*
입력할 데이터의 개수 입력 : 11
데이터 입력 : 54654
데이터 입력 : 231768
데이터 입력 : 15
데이터 입력 : 5
데이터 입력 : 9
데이터 입력 : 7
데이터 입력 : 7
데이터 입력 : 7
데이터 입력 : 6
데이터 입력 : 6
데이터 입력 : 897654
찾을 데이터 입력 : 7
key는 3개 있습니다.
*/

 

보초법(Sentinel Method)

선형 검색은 반복할 때마다 

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

위 두 종료 조건을 모두 판단한다. 단순한 판단이라고 생각할 수 있지만 티끌모아 태산이란 말이 있듯이 종료 조건을 검사하는 비용은 결코 무시할 수 없다.

이 비용을 절반으로 줄이는 방법이 보초법이다.

위 그림에서 배열 인덱스 0~6은 초기에 준비해 놓은 데이터이고, 검색하기 전에 검색하고자 하는 키 값을 맨 인덱스 7에 저장한다. 이때 저장하는 값을 보초라고 한다.

원하는 값이 원래의 데이터에 존재하지 않아도 보초인 인덱스 7까지 검색하면 종료 조건 2가 성립한다 이렇게 하면 원하는 키 값을 찾지 못했을 때를 판단하는 종료 조건인 1이 없어도 된다.

보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

public class Main{
	static int seqSearch(int[] arr, int key)
	{
		arr[arr.length-1] = key; //보초 추가
		int i;
		for(i = 0; i < arr.length; ++i) {
			if(arr[i] == key) break;
		}
		return i == arr.length-1 ? -1 : i;
	}
	
	public static void main(String[] args) {
		int arr[] = new int[8];
		arr[0] = 22; arr[1] = 8; arr[2] = 55; arr[3] = 32; arr[4] = 120; arr[5] = 55; arr[6] = 70;
		
		System.out.println("key의 인덱스는 " + seqSearch(arr, 120) + " 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)");
	}
}
/*
key의 인덱스는 4 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)
*/

선형 검색에선 return문이 두 개였는데, 보초법에선 return문이 한 개다.  이유는 종료 조건 1이 필요하지 않기 때문이다. 

따라서 반복 종료에 대한 판단 횟수는 절반으로 줄어든다.

반복문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 한다. 변수 i의 값이 배열의 길이를 -1을 한 값과 같다면 찾은 값이 보초이므로 -1을 리턴한다.