Keep going
이진 검색 본문
<이진 검색>
이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.
처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
키를 이진 검색으로 검사하는 과정을 일반적인 방법으로 표현해 보겠습니다.
검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정하겠습니다.
검색을 시작할 때 pl은 0, pr은 n-1, pc는 (n-1)/2로 초기화 합니다.
여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으로 좁혀 진다는 것 입니다.
오름차순으로 정렬된 데이터에서 39를 검색하는 과정을 생각해 보겠습니다.
| 5 (pl) | 7 | 15 | 28 | 29 (pc) | 39 | 58 | 68 | 95 (pr) |
| 39 (pl) | 58 (pc) | 68 | 95 (pr) |
| 39 (pl, pr) |
1. a[pc] < key
a[pl] ~ a[pc] 는 key보다 작은 것이 분명하므로 검색 대상에서 제외됩니다. 검색 범위는 중앙 요소 a[pc]보다 뒤쪽의 a[pc+1] ~ a[pr]로 좁힙니다. 그런 다음 pl의 값을 pc+1로 업데이트 합니다.
2. a[pc] > key
a[pl] ~ a[pc] 는 key보다 큰 것이 분명하므로 검색 대상에서 제외됩니다. 검색 범위는 중앙 요소 a[pc]보다 앞쪽의 a[pl] ~ a[pc-1]로 좁힙니다. 그런 다음 pr의 값을 pc-1로 업데이트 합니다.
이진 검색 알고리즘의 종료 조건
1. a[pc] 와 key가 일치하는 경우
2. 검색 범위가 더 이상 없는 경우 (pl이 pr보다 커지면서 검색 범위를 더 이상 계산할 수 없게 된다)
이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n입니다.
검색에 실패한 경우는 ┌log(n+1)┐회, 검색에 성공한 경우는 대략 log n-1회이다.
이진 검색을 java로 구현해보겠습니다.
|
package Chapter03;
import java.util.*;
class BinSearch {
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 (key > a[pc])
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return -1;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("요솟수 : ");
int size = input.nextInt();
int[] x = new int[size];
for (int i = 0; i < x.length; i++) {
x[i] = input.nextInt();
}
Arrays.sort(x); // 배열 오름차순 정렬하는 메소드
System.out.print("키 값 : ");
int key = input.nextInt();
int index = binSearch(x, size, key);
if (index == -1)
System.out.println("찾는 값이 존재하지 않습니다.");
else
System.out.println(key + "는 x[" + index + "]에 있습니다.");
}
}
|
cs |
출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]