자료구조&기본 알고리즘 입문(자바)- 검색 알고리즘, 선형 검색

○ 검색과 키
주소록을 검색 한다고 가정해보았을 때, 검색(Searching)은 다음과 같은 과정으로 이루어 진다

1. 국적이 한국이 사람을 찾음
2. 나이가 21세 이상 27세 미만
3. 찾으려는 이름과 가장 비슷한 이름의 사람 

어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 '검색하기'의 공통점.
그 주목하는 항목을 키(key). 국적을 검색하는 경우 국적이 키이고 나이를 검색하는 경우 나이가 키.
데이터가 단순한 정숫값이면 데이터값을 키 값이라고 생각해도 좋지만 대부분의 경우 키는 데이터의 '일부'.

위의 검색 과정을 보면 키 값을 하단과 같이 지정하고 있다.

1. 키 값과 일치하도록 지정(한국)
2. 키 값의 구간을 지정(21세 이상 27세 미만)
3. 키 값과 비슷하도록 지정(발음이 가장 비슷한 이름)

이런 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 복합해서 지정하기도 한다. 

 

○ 배열에서 검색 

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
3. 해시법: 추가, 삭제가 자주 일어나는 데이터 오임에서 아주 빠른 검색을 수행 
  -체인법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
  -오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법 

어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지인 경우 용도나 목적, 실행속도, 자료구조 등을 
고려하여 알고리즘을 선택해야 한다. 

 

○ 선형검색

배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘. 
요소가 직젓ㄴ 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search)또는 순차 검색(sequential search)이라는 알고리즘이다. 

배열의 요소를 맨 앞부터 순서대로 검색하는데, 검색이 성공하는 경우/검색에 실패하는 경우로 보면
배열 검색의 종료 조건은 2가지 이다. 다음 조건중 하나라도 성립하면 검색을 종료한다 

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

조건 1이 성립하면 검색 실패, 조건2가 성립하면 검색 성공이며 배월의 요솟수가 n개일때 조건1/2를 판단하는 횟수는
평균 n/2회이다. 

 

import java.util.Scanner;
// 선형 검색

class SeqSearch {
	// 배열 a의 앞쪽 n개의 요소에서 key와 같은 요소를 선형 검색 
	static int seqSearch(int[] a, int n, int key) {
		int i = 0;

		while (true) {
			if (i == n)
				return -1;		// 검색 실패(-1을 반환)
			if (a[i] == key)
				return i;		// 검색 성공(인덱스를 반환)
			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];		// 요솟수가 num인 배열

		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 = seqSearch(x, num, ky);	// 배열x에서 키 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}

위의 메서드  SeqSearch는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고
검색한 요소의 인덱스를 반환한다. 또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 
발견한 요소의 인덱스가 된다. 값이 key인 요소가 존재하지 않으면 -1을 반환한다. 

 

배열을 검색할 때 배열 요소의 인덱스를 카리키는 변수는 i. i는 0으로 초기화하고 요소를 하나 검색할 때마다 
while문이 제어하는 루프 본문의 끝에서 증가시킨다. while문을 빠져 나가는 경우는 아래와 같다

1. i==n이 성립하는 경우(검색 실패이므로 -1을 반환)
2. a[i]==key가 성립하는 경우(검색 성공이므로 i를 반환)

위의 배열 검색을 while 문이 아니라 for문으로 구현하면 프로그램은 보다 짧고 간결해진다.

import java.util.Scanner;
// 선형 검색 (for문)

class SeqSearchFor {
	// 배열 a의 앞쪽 n개의 요소에서 key와 같은 요소를 선형 검색 
	static int seqSearch(int[] a, int n, int key) {
		for (int i = 0; i < n; i++)
			if (a[i] == key)
				return i;			// 검색 성공!(인덱스를 반환)
		return -1;					// 검색 실패!(-1을 반환)
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("요솟수：");
		int num = stdIn.nextInt();
		int[] x = new int[num];					// 요솟수 num인 배열

		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 = seqSearch(x, num, ky);		// 배열x에서 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println("그 값은 x[" + idx + "]에 있습니다.");
	}
}

 

○ 보초법
선형 검색은 반복할 때 마다 다음의 종료조건 1과 2를 모두 판단한다. 단순한 판단이라고 생각할 수 있지만
종료조건을 검사하는 비용은 결코 무시할 수 없다.

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

이 비용을 반으로 줄이는 방법이 보초법(sentinel method)이다. 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장하고, 이떄 저장하는 값을 보초(sentienl)라고 한다. 
원하는 값이 원래의 데이터에 존재하지 않아도 보초를 검색하면 종료 조건2가 성립한다. 이렇게 하면 원하는 키 값을 
찾지 못했을 떄를 판단하는 종료 조건1이 없어도 된다. 
보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다. 

 

import java.util.Scanner;
// 선형 검색(보초법)

class SeqSearchSen {
	// 요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색.
	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 + "]에 있습니다.");
	}
}

검색할 값 key를 보초로 a[n]에 대입하고, 배열 요소를 순서대로 검사한다. 이전에서본 while문에는 if문이 2개가 있었으나 여기서는 if(i==n)이라는 종료조건 1이 필요하지 않기 때문에 하나의 if문을 사용했다. 따라서 반복 종료에 대한 판단 횟수는 실제로 절반으로 줄어든다. 
while문에 의한 반복이 완료되면 찾은 값이 배열의 우너래 데이터인지 아니면 보초인지 판단하는데, 변수 i값이 n이면 찾은 값이 보토이므로 검색 실패임을 나타내는 -1을 반환한다. 

 

-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893