이진 탐색(Binary Search) 알고리즘
- 정렬된 데이터가 아니면 적용이 불가능하다.
예를 들어 아래과 같은 배열이 있을 때,
1
|
int arr[9] = { 1,2,3,7,9,12,21,23,27 };
|
이 배열을 대상으로 숫자 3이 저장되어 있는지 확인하기 위해 이진 탐색 알고리즘을 적용해보면
이진 탐색 알고리즘의 첫 번째 시도
1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.
2. 0과 8을 합하고 그 결과를 2로 나눈다.
3. 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.
이진 탐색 알고리즘의 두 번째 시도
1. arr[4]에 저장된 값과 탐색 대상인 숫자 3의 대소를 비교한다.
2. 대소 결과는 arr[4] > 3 이므로 탐색의 범위 인덱스를 0~3으로 제한한다.
3. 0과 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.
4. 결과 1을 인덱스 값으로 하여 arr[1]에 저장된 값이 3인지 확인한다.
위와 같은 작업을 반복한다.
이렇듯 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다.
BinarySearch.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <stdio.h>
int BSearch(int arr[], int len, int target) {
int first = 0;
int last = len - 1;
int mid;
while (first <= last) {
mid = (first + last) / 2;
if (target == arr[mid]) {
return mid;
}
else {
if (target < arr[mid]) {
last = mid - 1;
}
else {
first = mid + 1;
}
}
}
return -1;
}
int main(void) {
int array[] = {1,3,5,7,9};
int idx;
idx = BSearch(array, sizeof(array)/sizeof(int), 7);
if (idx == -1) {
printf("탐색 실패 \n");
}
else {
printf("타겟 저장 인덱스 : %d \n", idx);
}
}
|
이진 탐색 알고리즘의 시간 복잡도
- 8을 예로 들어 계산해보면 8이 1이 되기까지 2로 나눈횟수 3회 + 데이터가 1개 남았을 때 마지막 비교 연산 1회로 총 4회이다.
- 즉, n이 1이 되기까지 2로 나눈 횟수 k + 마지막 비교 연산 1회. 시간 복잡도 T(n) = k + 1 이다.
- 수식으로 나타내면 n * 2^(-k) = 1 -> k = log_2n 따라서 시간 복잡도 T(n) = log_2n 이다.
- 여기서 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적으로 증가한다는 사실이기에 +1은 중요하지 않다.
출처 : 윤성우, 「윤성우의 열혈 자료구조」, 오렌지미디어(2019), p24-p34
'공부 > 자료구조' 카테고리의 다른 글
[자료구조] 리스트 (0) | 2021.01.03 |
---|---|
[자료구조] 재귀 (0) | 2020.04.16 |
[자료구조] 자료구조와 알고리즘의 이해 (3) - 빅-오 표기법 (0) | 2020.01.13 |
[자료구조] 자료구조와 알고리즘의 이해 (1) - 자료구조 (0) | 2020.01.04 |