[2] 이원 탐색(binary search)
binary search는 정렬되어 있는 배열을 가정하고 있습니다.
따라서 binary search를 이용하려면 우선적으로 배열을 정렬해야 합니다!
배열이 오름차순으로 정렬되어있다고 가정합시다.
binary search는 찾고자 하는 수와 가운데 수의 크기를 비교하고,
만약 찾으려고 하는 수보다 가운데 수가 더 크다면
-> 찾으려고 하는 수는 가운데 수보다 더 왼쪽에 존재한다는 의미!
-> 따라서 가장 왼쪽과 중간을 새로운 배열로 잡아서 해당 배열의 가운데 수로 동일한 과정 반복!
만약 찾으려고 하는 수보다 가운데 수가 더 작다면
-> 찾으려고 하는 수는 가운데 수보다 더 오른쪽에 존재한다는 의미!
-> 따라서 중간 수와 가장 오른쪽 수를 새로운 배열로 잡아서 해당 배열의 가운데 수로 동일한 과정 반복!
예시를 볼까요??
이 배열에서 14를 찾아본다고 합시다!
가운데 수인 12와 찾으려고 하는 수인 14을 비교했을 때 14가 더 크니까
12보다 오른쪽에 14가 존재한다는 말이겠네요!
따라서
색칠한 부분만 다시 고려합니다!
색칠한 부분에서 가운데는 16일까요 18일까요?
이는 정하기 나름이지만 C언어는 '/' 연산을 할 때 버림을 하니까
중간을 16이라고 봅시다.
16과 14를 비교하면 16이 더 크니까
14는 16보다 왼쪽에 있다는 뜻이겠네요!
따라서
다음과 같이 색칠된 부분만 다시 고려합니다!
여기서 중간 수는
14이고 이것이 바로 우리가 찾는 수네요!
binary search 완성!
C언어로 구현
위에서 한 예시를 C언어로 구현해봅시다!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// x > y 면 1, x == y 면 0, x < y 면 -1 을 리턴하는 매크로
#define COMPARE(x, y)((x) < (y) ? -1 : (x) == (y) ? 0 : 1)
/*
search_num을 찾으면 해당 index를 리턴한다.
만약 search_nun이 배열에 없으면 -1을 리턴한다.
*/
int binary_search(int list[], int search_num, int left, int right) {
int middle;
while (left <= right) {
middle = (left + right) / 2;
switch (COMPARE(list[middle], search_num)) {
case -1: left = middle + 1; break;
case 0: return middle;
case 1: right = middle - 1;
}
}
return -1;
}
|
cs |
O(logn)의 시간복잡도를 가집니다.