IV. Binary Search

• Binary Search
• Bisection (parametric) Search
• Ternary Search

Binary Search

Up & Down 게임을 해 보셨나요? 1부터 1000까지의 수 중 하나를, 10번 정도면 맞출 수 있다는 사실을 알고 계시나요? 아마도, 모두가 절반씩 잘라서 확인하는 전략을 사용할 것입니다. 이 전략을 우리는 Binary Search 라고 부릅니다.
$N$ 크기의 배열이 정렬되어 있음을 안다면, 이 Up & Down 전략을 이용하여, 우리는 한번 질문할 때마다 절반씩 문제의 크기를 줄일 수 있습니다. 예를 들어, 10개짜리 배열의 5번을 열어 봤는데 우리가 원하는 값보다 크다면, 1번부터 4번 사이에 원하는 값이 있음을 아니까 2번이나 3번을 물어보면 됩니다. 이렇게 하면, $\order{\log n}$ 시간에 정렬된 배열에서 특정한 값을 찾을 수 있습니다. 이 알고리즘은 정말 유용합니다! Programming Practice들을 풀면서 확인해 보세요 :)

Bisection (parametric) Search

Binary Search를 확인하여, 다음과 같은 질문에 빠르게 답할 수 있습니다.
어떤 함수 $f : \R \to \R$가 단조 증가하는 연속 함수일 때, $f(x) = k$ 인 $x$를 찾아라.
정확히 말하자면, 이 질문에 정확하게 답할 필요까지는 없고, 충분히 가까운 $x$를 찾으면 됩니다. 이제, $f$가 단조증가한다는 성질을 이용하여, 충분히 작은 수와 충분히 큰 수로 양쪽 끝값을 잡아 놓고, 그 사이를 구간으로 이분 탐색합니다.
예를 들어, $2^{1/3}$ 을 계산해야 한다고 생각해 봅시다. 이때, 우리는 답이 되는 $x$가 $x^3 = 2$ 를 만족하며, 이 값이 $0$과 $2$ 사이에 있음을 압니다. 이 구간의 중간인 $1$을 이용하여, $1^3 = 1 < 2$ 이므로, 답이 $1$과 $2$ 사이임을 압니다. 이제, $1.5^3 > 2$ 이므로, 답이 1과 $1.5$ 사이임을 압니다. 이제 $1.25$를 시도하고...
이 알고리즘을 Parametric Search라고 합니다 (사실은, 이 단어는 더 일반적인 상황에서 쓰는 말입니다. 굳이 말하자면 Bisection search 정도가 정확할 것 같은데, 우리가 관심있는 Parametric Search가 이쪽이 대부분이라서 그런 것 같기도 합니다). Parametric Search는 Binary Search의 일반화이면서, 정말 많은 것들을 할 수 있습니다. 앞으로 대회 준비나 공부를 더 하다 보면, 이 아이디어를 이용하는 문제를 정말 많이 만나게 됩니다.
Parametric과 Binary 를 구분하지 않고 Binary Search를 이용한다고 말하는 사람도 많이 있고, 사실 이걸 굳이 구분할 필요가 있다고 생각하지는 않습니다. Binary라고 쓰더라도 맥락에 따라 이해해 주세요.

Ternary Search

* 이 subsection을 skip해도 뒤 내용에 영향이 없습니다.
어떤 함수 $f : \R \to \R$가 볼록함수라고 할 때, $f(x)$ 의 최솟값을 찾는 문제를 생각해 봅시다. 만약 $f$가 미분 가능한 함수라면, $f$의 도함수를 생각했을 때, $f’(x) = 0$이 되는 $x$를 Binary Search로 찾는 방법을 생각할 수 있겠습니다. 그러나 우리가 생각하는 함수가, ‘대충 볼록하게 생기긴 했지만’ 미분이 가능하진 않을 수도 있습니다. 이경우에, $\log$ 시간에 최솟값을 찾는 방법을 생각해 봅시다. 단, 이 함수 $f$가 평평한 구간을 갖지 않는다고 합시다.

• 충분히 작은 $L$과 큰 $R$을 생각합니다.

• $[L, R]$의 삼등분점인 $p, q$를 생각합니다.

• 일반성을 잃지 않고, $f(p) > f(q)$ 라고 가정합시다. 이때, 만약 최솟값이 $[L, p]$에 있고, 그 최소점이 $x = t$라면, 함수가 적어도 $t$에서 $p$까지 사이에서 증가하는 구간이 있고, 다시 $q$까지 감소해야 합니다. 이는 $f$의 볼록성과 모순이므로, 최솟값이 $[p, R]$ 사이에 있습니다.

• 우리가 보는 구간의 길이가 $\frac{2}{3}$으로 줄어들었습니다!

이제, 생각해 보면 매번 $2/3$으로 구간을 줄이는 것이므로, $\log_{3/2} n$ 시간에 ($n$은 우리가 필요한 정밀도와, 구간 길이의 비율입니다. 간단히 말해, $[0, 10]$ 사이에서 $0.001$ 수준의 정밀도를 얻는 것은 1만 칸 중 하나를 찾는 느낌으로 접근하면 된다는 얘기입니다) 답을 얻을 수 있고, Asymptotic하게는 로그의 밑은 무의미하므로 $\log$ 시간 알고리즘이 됩니다. 이 알고리즘을 Ternary Search, 삼분 탐색이라고 부릅니다.

이분 탐색이나 삼분 탐색은 그 자체로도 매우 의미있지만, 다른 알고리즘과 결합되었을 때 그 유용성이 더욱 부각됩니다. 그리고 처음 접했을 때 생각해내기 어렵기 때문에, 많은 연습이 필요합니다.