나름 증명을 해보았습니다.

편의상 문제의 정답을 A라고 합시다.

count_below(middle) >= k라는 조건은 middle>A로 표현할 수 있겠습니다.

먼저 실행 초기에는 left<=A<=right이 성립하며, 이 조건을 만족하는 한 각 반복문의 실행 시마다 다음 세 가지 경우로 나눌 수 있습니다.

case 1: middle>A인 경우

이 경우 right <- middle-1이므로 다시 left<=A<=right이 성립하게 됩니다.

case 2: middle<A인 경우

이 경우 left <- middle+1으로 다시 left<=A<=right이 성립하게 됩니다.

case 3: middle=A인 경우

이 경우 일단 left <- middle+1이 실행되어 다시 다음과 같은 두 경우로 나눌 수 있습니다.

case 3-1: right=A인 경우

이 경우 left>right이 되어 바로 실행이 끝나며, 정답이 출력됩니다.

case 3-2: right>A인 경우

이 경우 left=A+1<=right이며 이 이후로 생성되는 모든 middle>A입니다. 즉, left>right이 되기 전까지 항상 right <- middle-1 연산만이 실행되며, 즉 루프 종료시 right=A가 되어 정답이 출력됩니다.

추가로, 루프가 언젠가 종료된다는 사실은 아마 어떻게든 쉽게 증명될 겁니다.

답변 감사합니다~

혹시 답변해주신 내용이 종료조건에 관련된 내용일까요?

제가 궁금했던 내용은 binary search로 0에서 N^2 사이에 있는 수를 가지고 조건을 테스트하게 되는데

배열 A에는 0부터 N^2 사이의 수 중에서 없는 수가 있는데 혹시 binary search를 하면서 이 없는 숫자에서 루프가 종료되게 된다면

오답이 출력되지 않을까 하고 질문드린겁니다!

예를 들어 N이 3일 때

A =

1 2 3

2 4 6

3 6 9 

가 되므로 배열에 5가 없습니다

K로 7이 주어졌을 때 원래대로라면 B = [1, 2, 2, 3, 3, 4, 6 ... 이므로 6을 출력해야 되는데

binary search를 하다가 만약에 5를 만나면 count_below를 만족하므로 5를 출력하지 않을까 궁금했습니다

N이 3일 때 5를 만나지 않는 것은 눈으로 따라가 보면 알겠는데 N이 더 커지게 되면 문제가 안 되는 것인지 궁금합니다.

아니면 5를 만나더라도 상관없는 건가요?

요약하자면 5가 조건을 만족하는 수기는 하지만 이 코드는 조건을 만족하는 가장 큰 수를 출력하므로 정상적으로 6이 출력됩니다.

조금 첨언을 하자면 저는

조건을 만족하는 가장 큰 수 = 경계값

으로 생각해보니, 경계값은 무조건 존재하는 숫자라는 걸 조금 더 직관적으로 이해할 수 있었습니다.