프로그래밍[Univ]/알고리즘
[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 2. 이진검색
Cloud Travel
2011. 10. 7. 20:20
1. 이진 검색(Binary Search)
- 문제 : 크기가 n인 정렬된 배열 S에 키(key) x가 있는지를 탐색
ⓐ 명확한 방법
- 알고리즘
① 키 x를 찾을 때까지 배열의 첫번째 요소부터 시작하여 x를 배열의 각 요소와 순서대로 비교한다.
- 복잡도 분석
> 최악의 경우 n번을 비교해야 한다.
- 관찰
> 이 방법은 "배열이 정렬되어 있다는 사실"을 이용하지 않고, "균형취하기"라는 발견법을 이용하지 않았다.
ⓑ 효율적인 방법
- 알고리즘
① 키 x를 배열의 중간요소와 비교한다. 같으면 찾았으니 끝낸다.
캍지 않으면, 배열을 중간요소를 기준으로 반을 나눈다.
② 키 x가 중간요소보다 작으면 왼쪽에 위치한 배열반쪽을 선택한다.
키 x가 중간요소보다 크다면 오른쪽에 위치한 배열의 반쪽을 선택한다.
③ 키 x가 선택한 반대 배열에 있는지를 결정하기 위해 회귀(recursion)을 사용한다.
즉, ①과 ②를 반복한다.
- 예제 : 다음 배열에서 키 x = 18을 찾아라.
배열 : 10 12 13 14 18 20 25 27 30 35 40 45 47
> x = 18을 배열의 중간요소인 25와 비교한다.
18이 25보다 작으므로 왼쪽에 위치한 배열반쪽에서 x를 찾는다.
검색할 배열 : 10 12 13 14 18 20
> x = 18을 중간요소인 13과 비교한다.
18이 13보다 크므로 오른쪽에 위치한 배열 반쪽에서 x를 찾는다.
검색할 배열 : 14 18 20
> x = 18을 중간요소인 18과 비교한다.
값이 같으므로 검색을 종료한다.
- 알고리즘 구현
> 입력 : 배열 S[low...high]와 키 값 x // low와 high는 배열의 최소와 최대 인댁스 값이다.
> 출력 : 배열 S내에서의 x의 위치 (x가 S안에 없다면 0)
int bin-search(int low, int high){
int mid;
if ( low > high ) return 0; // 값이 없을 경우
else{
mid = rounddown((low+high)/2); // mid값이 실수일경우 버림을 실시한다.
if( x == S[mid] ) return mid;
else if( x < S[mid] ) return bin-search(low, mid-1);
}
}
- 분석 : 최악의 경우에 대한 알고리즘의 실행트리를 보자.
