binary search
1
2
3
4
5
6
7
int search(int a[], int n, int x)
{
int i;
for(i=0; i<n; i++)
if(a[i] == x) return i;
return -1;
}
어떤 배열에서 원하는 값을 찾는 경우를 생각해보자.
배열의 길이가 N일 경우 앞에서부터 하나씩 보면 O(N)의 시간에 찾을 수 있다.
무언가를 찾아야 할 때 처음부터 끝까지 봐야한다면 비효율적인 것 같다.
그래서 정렬된 배열에서 O(logN)으로 빠르게 탐색할 수 있는 이분 탐색을 주로 사용한다.
어릴 때 하던 1~100까지 1명이 숫자를 생각하고 다른 사람이 맞추는 게임과 비슷하다.
숫자를 예측해 말하면 상대방은 생각한 숫자보다 작은지 큰지를 알려준다.
이 게임의 가장 효율적인 풀이 방법은 구간은 반으로 쪼개면서 물어보는 것이다.
0~100이므로 50, 작다고 하면 0~50이므로 25, 크다고 하면 25~50이므로 38…
과 같은 방법으로 하면 log100 = 7번만에 반드시 답을 찾을 수 있다.
우선 배열에서 원하는 N을 찾는 이분 탐색을 하기 위해서는 정렬이 되어있어야 한다.
그 다음 l을 v[0], r을 v[v.size()-1]로 놓는다.
이제 mid는 (l+r)/2가 된다.
mid와 N을 비교했는데 작다면 l = mid로 찾는 범위를 mid 오른쪽 부분으로 만들어주고
크다면 r = mid로 찾는 범위를 mid 왼쪽 부분으로 만들어준다.
이렇게 범위를 줄이다가 while(l+1 < r) l과 r사이에 다른 칸이 없을 때 종료하면 된다.
위의 gif로 더 쉽게 이해할 수 있다.
참고 : https://www.acmicpc.net/blog/view/109
이분 탐색은 위처럼 간단한 검색 방법으로 사용할 수도 있지만 나아가 여러 문제를 해결할 수 있다.
이분 탐색은 문제의 답이 YES or NO인 결정 문제에서 사용할 수 있는 탐색 기법이라고 생각하는 것이 좋다.
위의 숫자 찾기 문제는 v[i] >= N인가? 라는 질문을 던졌을 때
1
2
3
4
N = 5
1 3 4 5 7 8
F F F T T T
라는 결정 문제로 변환이 되고, F와 T의 분포가 경계를 기준으로 나눠져있다.
그리고 우리가 구하려는 답은 F에서 T로 넘어가는 i값이다.
이렇게 결정 문제의 parameter에 대해 T, F가 두 구간으로 나뉜다면 이분 탐색을 사용할 수 있다.
구현
1
2
3
4
5
6
7
int l = 0, r = 1e9;
while (l + 1 < r) { // lo와 hi 사이에 다른 칸이 존재하는가?
int mid = (l + r) >> 1;
if (Check(mid)) l = mid;
else r = mid;
}
위의 참고 글을 읽은 뒤로 이분 탐색을 구현할 때 이렇게 쓰고 있다.
while 조건 안에 l <= r, l < r 등이 들어갈 수도 있지만 (l+1) < r 방식이 가장 편하다.
그 이유는 결정 문제의 결과에 따라 l = mid, r = mid로 구간을 바꿀 수 있기 때문이다.
위의 코드의 Check()힘수는 mid를 parameter로 Yes / NO 결정 문제의 답을 반환하는 함수다.
구현할 때 주의점은 초기의 l과 r에 대해 Check(l) != Check(r)이어야 한다.
그러면 [l,r]범위 안에서 T, F가 바뀌는 경계가 있음이 보장된다.
이분 탐색이 끝났을 때, l과 r은 경계에 위치하고 경계를 기준으로 왼쪽과 오른쪽 중 어느 것이
답인지를 생각해서 l또는 r로 답을 도출할 수 있다.
풀면 풀수록 이분 탐색 문제들에도 재밌는 아이디어들이 많은 것 같다.