[1. Binary search, 이진탐색]
● 방식
→ A를 오름차순으로 정렬된 n개 요소들의 리스트라고 할 때,
→ 찾으려는 값 x가 A내에 몇 번째에 존재하는지 확인하는 알고리즘이다.
→ x를 A내의 요소들의 중앙값(A[m])과 비교하여
→ x = A[m]이면 m을 반환,
→ x < A[m]이면 다시 x를 A[s ~ m-1]에서 탐색,
→ x > A[m]이면 다시 x를 A[m+1 ~ e]에서 탐색하는 방식이다.
(* A내에 n개의 원소가 있다면 s=0, e=n-1)
● 알고리즘
→ Divide : m = (s+e)/2를 기준으로 배열을 분할
→ Conquer : A[s, m-1] 또는 A[m+1, e]
→ Degenerate case : A 또는 분할된 A 내에 원소가 하나인 경우 (s==e)
● 구현
#include <stdio.h>
int A[9] = { 1,2,3,4,5,6,7,8,9 };
int Binary_search(int s, int e, int* A, int x) {
if (s == e) { //Degenerate_case
if (A[s] == x)
return s;
else
return -1;
}
int m = (s + e) / 2; //Divide
if (A[m] == x) //Conquer
return m;
else if (A[m] > x)
return Binary_search(s, m - 1, A, x);
else
return Binary_search(m + 1, e, A, x);
}
int main() {
int x = 1;
int s = 0, e = 8;
int k = Binary_search(s, e, A, x);
printf("%d번째에 존재", k);
}
● 성능
→ 중앙값을 기준으로 배열을 절반씩 분할(n/2)하는 과정을 반복하고
→ 분할된 배열의 중앙값과 한번(1)씩 비교함
→ T(n) = T(n/2) + O(1) = O(logn)
(* 만약 재귀함수가 아닌 반복문을 사용할 경우, 성능은 O(n)으로 덜 효율적임)
'알고리즘 > Divide & Conquer' 카테고리의 다른 글
[알고리즘] Divide & Conquer (3) - Quick sort (2) | 2022.11.08 |
---|---|
[알고리즘] Divide & Conquer (2) - Merge sort (0) | 2022.11.08 |