자료구조&기본 알고리즘 입문(자바)- 이진 검색

○이진 검색
이 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되 이었다는 것. 
이진 검색은 선형 검색보다 좀 더빠르게 검색할 수 있다는 장점이 있다. 

이진 검색(binary search)은 요,소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 
알고리즘이다. 

오름차순으로 정렬된 데이터 39를 검색하는 과정을 생각해보자. 먼저 배열의 중앙에 위치한 
요소인 a[5]31부터 갬색을 시작한다. 

검색ㅎ하려는 값은 39는 중앙 요소(a[5])보다 큰 값이다(뒤쪽에 존재) 그러므로 검색 대상을 뒤쪽의 5개 
(a[6]~a[10])으로 좁힐 수 있다. 그럼 다음 검색 범위의 중앙에 위치한 요소은 a[8]이 원하는 값인지 확인한다. 

검색하려는 값인 39보다 큰 값이므로, 검색 대상을 앞쪽의 2개(a[6]~a[7])로 좁힐 수 있다. 이제 검색해야 하는 
대상은 2개고, 이 떄 두 요소의 중앙요소는 아무거나 선택해도 상관없지만 여기서는 앞쪽의 값을 선택하여
원하는 겂인지 확인한다. 

위와 같은 과정을  n개의 요소가 오름차순으로 늘어선 배열a에서 키를 이진 검색으로 검색하는 과정을 일반적인 방법으로 표현하자면, 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정한다. 
검색을 시작할 떄 pl은 0, pr은 n-1, pc는 (n-1)/2로 초기화한다.  검색대상의 범위는 이진 검색을 한 단계식 진행할 때마다 검색 범위가 반으로 좁혀진다. 또한 검사한 요소를  하나씩 제외시키는 선형 검색과는 다르게 이진 검색은 검색할 요소가 해당 단계에서 다음에 검색할범위의 중간 지점으로 단숨에 이동한다. 

원하는 값을 찾지 못하면 다음과 같이 검색 범위를 좁혀 갈 수 있다 

 

1. a[pc] < key 일때

a[pl]~a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다. 검색 범위는 중앙요소 a[pc]보다
뒤쪽의 a[pc+1]~a[pr]로 좁힌다. 그럼 다음 pl 값을 pc+!로 업데이트한다.

 

2. a[pc] > key 일떄

a[pc]~a[]r]은 key보다 큰 것이 분명하므로 검색 대상에서 제외한다. 검색 범위는 중앙요소 a[pc]보다 앞쪽

a[pl]~a[]c-1]로 좁힌다. 그런 다음 pr의 값을 pc-1로 업데이트한다. 

이진 검색 알고리즘의 종료 조건은 하단 조건중 하나만 성럽하면 된다

조건-1: a[pc]와 key가 일치하는 경우
조건-2: 검색 범위가 더 이상 없는 경우 

 

이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다. 
검색에 실패한 경우는 [log(n+1)]회, 검색에 성공한 경우는 대략 log n-1회다.

import java.util.Scanner;
// 이진 검색 

class BinSearch {
	// 요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색.
	static int binSearch(int[] a, int n, int key) {
		int pl = 0;			// 검색 범위의 첫 인덱스
		int pr = n - 1;		// 검색 범위의 끝 인덱스

		do {
			int pc = (pl + pr) / 2;		// 중앙 요소의 인덱스
			if (a[pc] == key)
				return pc;				// 검색 성공!
			else if (a[pc] < key)
				pl = pc + 1;			// 검색 범위를 뒤쪽 절반으로 좁힘
			else
				pr = pc - 1;			// 검색 범위를 앞쪽 절반으로 좁힘
		} while (pl <= pr);

		return -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인 배열

		System.out.println("오름차순으로 입력하세요.");

		System.out.print("x[0]：");			// 첫 요소 입력
		x[0] = stdIn.nextInt();

		for (int i = 1; i < num; i++) {
			do {
				System.out.print("x[" + i + "]：");
				x[i] = stdIn.nextInt();
			} while (x[i] < x[i - 1]);		// 바로 앞의 요소보다 작으면 다시 입력
		}

		System.out.print("검색할 값：");		// 키값을 입력
		int ky = stdIn.nextInt();

		int idx = binSearch(x, num, ky);	// 배열x에서 값이 ky인 요소를 검색

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

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