안녕하세요!
이번 포스트에서는 binary search에 대해 이야기 해보겠습니다.
binary search, 이분 탐색은 어떤 정렬된 범위 내에서 우리가 원하는 값을 빠르게 찾기 위한 탐색 방식입니다.
예시 문제
https://www.acmicpc.net/problem/1920 수 찾기
n개의 정수열 중에 어떤 숫자 X가 존재하는지 판단하는 문제입니다.
평범하게 구현했을 때, X가 존재하지 않는 최악의 경우 n개의 모든 숫자를 돌아보아야 하므로 시작복잡도는 O(n)이 됩니다.
하지만 이분 탐색을 이용하면 O(n)을 O(log n)으로 줄일 수 있습니다.
이게 얼마나 빨라진 거냐면, 2^100번 돌아야하는 작업을 100번만 돌아서 끝낼 수 있다는 뜻입니다.
2^100을 계산기에 넣어보니 31자리 숫자가 나오네요.
아빠가 빌게이츠면 1초만에 돌아갈지도…?
문제 풀이
이제 문제를 풀어봅시다!
이분 탐색은 기본적으로 ‘정렬된’ 숫자열에서 동작합니다.
다음과 같은 수열을 가정해봅시다.
찾는 수 X: 4
번지: 0 1 2 3 4 5 7
수열: 1 2 4 5 6 8 9
left = 0, right = 7, mid = (left + right) / 2 = 3으로 두고 시작합니다.
편의상 수열이 담긴 배열을 A라고 하겠습니다.
먼저 A[mid = 3]를 봅니다.
A[mid = 3]는 5로, 우리가 찾는 X인 3보다 큽니다.
따라서 우리는 더 작은 범위인 왼쪽을 탐색해야하므로
right는 mid - 1 = 2로 옮겨주고, mid는 mid의 왼쪽 범위인 (left + mid) / 2 = 1로 옮겨줍니다.
다시 A[mid]를 봅니다.
A[mid = 1]는 2로, 우리가 찾는 X인 4보다 작습니다.
따라서 우리는 더 큰 범위인 오른쪽을 탐색해야하므로
left는 mid + 1 = 2로 옮겨주고, mid는 mid의 오른쪽 범위인 (mid + right) / 2 = 2로 옮겨줍니다.
다시 A[mid]를 봅니다.
A[mid = 2]는 4로, 우리가 찾는 X인 4와 일치합니다!
이로써 우리는 최대 2^3번의 탐색을 3번의 탐색으로 줄였습니다.
그렇다면 수가 존재하지 않는 경우는 어떤 경우일까요?
left <= right를 만족하지 않는 경우입니다.
right = mid - 1, left = mid + 1을 계속 하다보면 언젠가는 left와 right가 교차하는 경우가 생깁니다.
멋지게 그림 그려서 설명하고 싶은데 그림 그리기도 귀찮고 어떻게 올리는지도 모르겠네요.
아무튼 그렇습니다.
코드
int n = 8, x = 4, a[] = {1,2,4,5,6,8,9};
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x) {
// we got it!
break;
}
else if (a[mid] > x) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
추가
문제 풀이에서 이분 탐색을 다양하게 응용할 수 있습니다.
else if (a[mid] > x) 이 부분에서 a[mid] > x 대신에 어떤 함수를 넣어도 됩니다.
함수의 리턴값이 -1이면 왼쪽, 1이면 오른쪽, 0이면 ㅇㅋㅇㅋ 이런식으로요.
어떤 process가 x = mid일 때 만족하는지 검사하면서 x의 최솟값을 찾아도 되고
아무튼 그렇습니다.
끝
뭔가 멋지게 써보고 싶었는데 완전 날림으로 썼네요.
다른 블로그에 더 멋진 설명이 많습니다.
다음 포스트는 bfs와 dfs로 쓰려고 하는데 그래프 그리기가 막막해서 다음 포스트는 없을지도 모르겠네요 (…)
아무튼 읽어주셔서 감사합니다. (__)
아무말
이분 탐색, binary search, 이진 탐색, 알고리즘, 자료구조, log n