검색 알고리즘 ?

데이터 집합에서 원하는 값을 가진 요소를 찾아낸다.

1. 선형 검색 (Linear, Sequential Search)
2. 이진 검색 (Binary Search)
3. 해시법 : 체인법, 오픈 주소법

검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 되지만 검색 이외의 작업이 필요하다면 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다.

---

선형 검색

Linear Search Binary Search
요소가 직선 모양으로 늘어선 배열에서, 원하는 키 값을 갖는 element를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.

선형 검색의 종료 조건은

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

이 두 가지가 있다.

선형 검색 기본 연습

import java.util.Scanner;

public class SequentialSearch {

	static int sequential(int[] a, int n, int key) {
		for (int i = 0; i < n; i++)
			if (a[i] == key)
				return i; // 검색 성공
		return -1; // 검색 실패
	}

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

		System.out.print("num of element :");
		int num = sc.nextInt();
		int[] a = new int[num]; // num개의 element를 가진 배열

		for (int i = 0; i < num; i++) {
			System.out.print("a[" + i + "] : ");
			a[i] = sc.nextInt(); // 배열 입력받기
		}

		System.out.print("검색할 값 : ");
		int key = sc.nextInt();

		int result = sequential(a, num, key);

		if (result == -1)
			System.out.println("검색 실패");
		else
			System.out.println("a[" + result + "] : " + key);
	}

}

num of element :8
a[0] : 23
a[1] : 4     //중복된 값이 있으면 가장 먼저 찾은 값을 반환한다.
a[2] : 25
a[3] : 4
a[4] : 36
a[5] : 7
a[6] : 8 
a[7] : 9
검색할 값 : 8
a[6] : 8

보초법

sentinel method
종료 조건이 2개인 선형 검색의 비용을 반으로 줄이는 방법이다.

- 검색할 key 값을 보초로 배열의 마지막 요소에 넣는다.

검색 성공 : 검색할 값과 같은 요소를 발견한다.
검색 실패 : 보초로 넣은 값을 발견한다. 

원하는 키 값을 찾지 못했을 때 판단하는 종료조건이 없어지므로, 종료 판단 횟수가 반으로 줄어들게 된다.

보초를 넣어주었으므로, 배열 요소 값 +1 해주기!