[알고리즘] 이분 탐색

서론

이분 탐색 알고리즘은 이해하는 것은 어렵지 않은 알고리즘이라고 생각합니다. 주로 정렬되어 있는 배열에서 특정 값이 존재하는지 찾는 데 매우 유용한 알고리즘이고 선형탐색으로 O(N)의 시간복잡도가 걸리는 작업을 O(logN)으로 해결할 수 있습니다.

하지만 막상 구현에 들어가게 되면 맞게 구현한 것 같은데, 원하는 결과가 나오지 않는 경우가 종종 있어 검색을 통해 이분 탐색의 정확한 정의와 구현 방법을 배우고자 하였습니다. 그 과정에서 정리가 매우 잘 되어 있는 글을 찾게 되었고, 이번 글은 https://www.acmicpc.net/blog/view/109 을 올려 주신 jinhan814님의 글을 보고 정리한 글입니다.

해당 글에 정말 자세하게 이분 탐색 알고리즘에 대해 정리되어 있으니 참고하시면 큰 도움이 될 것 같습니다.

 

결정 문제와 이분 탐색의 활용처

이분 탐색은 결정 문제에서 답이 이분적일 때 사용할 수 있는 탐색 기법입니다.

결정 문제란 답이 T 또는 F으로 나누어지는 문제를 의미합니다.

예를 들어 1 ~ 50까지 오름차순으로 정렬된 배열에서 28을 찾는 문제를 해결해 봅시다.

이 경우 결정 문제를 arr[i] ≥ 28으로 잡게 된다면 i가 증가함에 따라 F, F, F, … , T, T… T가 될 것입니다.

결정 문제의 답이 두 구간으로 나뉘는 것을 이분적이라고 하며 이분 탐색을 통해 최종적으로 결정 문제의 답이 달라지는 경계를 찾을 수 있습니다.

 

이분 탐색의 아이디어와 결과

경계를 포함하는 [lo, hi] 구간을 잡아 길이를 절반씩 줄여나가며 lo, hi를 경계 지점에 위치하도록 합니다. 이분 탐색이 끝난 후의 결과는 lo 다음의 값은 hi가 되며, check(lo) ≠ check(hi)가 됩니다.

 

이분 탐색의 구현

• check(lo) ≠ check(hi)가 되도록 lo, hi의 초기값을 설정합니다.
• 우선 check(lo) ≠ check(hi)이기 때문에 [lo, hi]의 구간에 결정 문제의 답이 바뀌는 경계가 항상 존재함을 알 수 있습니다.
• while (lo +1 < hi) 인 동안 check(lo) == check(mid)라면 lo = mid, check(hi) == check(mid)라면 hi = mid가 됩니다.→ 반복문을 탈출했다면 lo + 1 ≥ hi 인 경우이고 항상 lo+1 == hi을 만족하게 됩니다.
• 범위를 줄여나가는 과정에서 check(lo) 값과 check(hi)가 변하지 않습니다.

이분 탐색이 끝나면 lo, hi는 결정 문제의 답이 바뀌는 경계에 위치하게 되고, 만약 결정 조건의 분포가 F~T이라면 가장 큰 F는 lo가 되고, 가장 작은 T는 hi가 되는 걸 알 수 있습니다.

 

추천 알고리즘 문제

백준 2805 나무자르기

https://www.acmicpc.net/problem/2805

백준 1477 휴게소세우기

https://www.acmicpc.net/problem/1477

백준 16434 드래곤앤던전

https://www.acmicpc.net/problem/16434