정답을 구할 수 없지만, X가 가능한지 아닌지 알아내는 것이 가능한 문제를 풀 때 이분탐색을 활용한다.
EX) A에서 B까지 X라는 시간으로 이동할 수 있는가 ?
이렇게 YES/NO의 형태로 주어진 답을 이용해 정답을 구할 수도 있다. 예를 들어 A에서 B까지 가는 가장 빠른 시간을 구하는 것이 문제라고 해보자. 정답이 “양의 정수”라고 할 때, 1, 2, 3, …을 차례로 X에 대입하여 A에서 B까지 갈 수 있는 X라는 시간 중 가장 빠른 것을 구하면 된다.
EX) 문제 : 사무실에 있는 TV의 크기가 X인치 이하인가 ?
위 문제에서 정답이 7인치라고 할 때, 1부터 6인치까지로 질문했을 때 NO를, 7인치부터 그 이상을 질문했을 때는 YES를 말해야한다. 따라서 이 문제를 이분 탐색으로 풀 수 있다.
1부터 99까지의 범위라고 하자. 50인치 이하가 아니다 라는 것을 알게 되면, 1부터 50은 모두 버려도 된다. 다시 51부터 99까지 범위를 바꾸고 75인치 이하다라는 것을 알게 되면, 51부터 75까지 범위를 바꾸고 다시 탐색한다.
정답의 범위가 절반씩 나누어지고 있으므로 최대 N개의 숫자에 대해서 logN의 시간 복잡도가 걸린다.
실제로 수를 만드는 것은 시간이 너무 오래 걸려서 불가능하다. 이분 탐색으로 N을 정하고, 그 때마다 수의 길이를 계산하여 K보다 작거나 같은지 계산한다.
예를 들어 N = 20, K = 23일 때 자릿수의 길이는 31이다. K가 이 길이보다 작기 때문에 가운데 10을 기준으로 삼아 1~10을 검사한다. 이 때는 자릿수의 길이가 11이 나오게 되고, K보다 크기 때문에 오른쪽을 택한다.
이 과정으로 경우의 수는 log(10억) = 약 30의 시간이 걸리게 된다.
1 ~ 9 까지의 자릿수 : (9 -1 + 1) * 1
10 ~ 99까지의 자릿수 : (99 - 10 + 1) * 2
100 ~ 999까지의 자릿수 : (999 - 100 + 1) * 3 …
이 값을 모두 더하면 1부터 n까지의 자릿수를 구할 수 있다.