이분 탐색(Binary Search)이란 특정 값을 비교적 빠르게 찾는 알고리즘입니다.
선형 탐색의 경우 N개 값 중에 T라는 값을 찾는다면 최악의 경우 O(N)의 시간 복잡도를 가집니다.
하지만 이분 탐색은 최악의 경우 O(logN)의 시간 복잡도를 가집니다.
이분 탐색은 1가지 조건이 필요합니다.
- 입력받은 값들이 정렬되어 있어야합니다.
이분 탐색은 특정 값을 찾을 때 탐색 범위를 절반씩 나눠가며 값을 찾는데, 이때 절반으로 나누는 기준이 값의 크기입니다. 크기에 따라 나누어진 절반의 오른쪽 범위인지, 왼쪽 범위인지를 구별합니다.
이분 탐색의 기본 로직은
- 처음에 Left, Right 값을 인덱스의 시작, 끝으로 초기화한다.
- Left, Right의 중간 위치의 값이 찾는 값 T보다 크면 Left를 중간 다음 위치로, 작으면 Right를 중간 이전 위치로 값을 정한다
- 2번의 과정을 값을 찾을 때까지 반복한다.
#include <stdio.h>
int main(void)
{
int T;
int result = 0;
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };
scanf("%d", &T);
int left = 0, right = 9;
while (left <= right)
{
int mid = (left + right) / 2;
if (a[mid] > T)
right = mid - 1;
else if (a[mid] < T)
left = mid + 1;
else
{
result = mid;
break;
}
}
printf("%d\n", result);
return 0;
}
위 과정을 통해서 탐색을 하면 탐색 범위는
(1 / 2)^K * N (K는 탐색 횟수)
만큼 작아질 것이며, K ≈ logN이 된다.
즉, 시간 복잡도는 O(logN)이 된다.
'Algorithm' 카테고리의 다른 글
가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) (0) | 2020.04.07 |
---|---|
Lower Bound & Upper Bound (0) | 2020.04.03 |
[정렬] 선택 정렬 (Selection Sort) (0) | 2020.01.20 |
[정렬] 삽입 정렬 (Insertion Sort) (0) | 2020.01.20 |
[정렬] 버블 정렬 (Bubble Sort) (0) | 2019.11.21 |