Counting Binary Search Guesses
National Olympiad — National round (2010 season)
Submission name: game.cpp
Problem summary
A secret k lies in [1, n]. Repeatedly guess floor((A + B)/2), initially A = 1 and B = n. If the guess is below k, set A = guess + 1; if above, set B = guess − 1. Count guesses including the successful one.
Input
Two integers n and k.
Output
The number of guesses until k is found.
Constraints
1 ≤ n ≤ 10^18; 1 ≤ k ≤ n.
Worked example
An independently prepared example for this explanation.
Input
9 6
Output
3
Solution analysis
- Simulate the exact strategy with lower and upper bounds. Compute the midpoint as lower + (upper − lower)/2, which avoids adding two large bounds.
- Increase the guess counter before comparing the midpoint to k. Return on equality; otherwise discard the half that cannot contain k.
- For n = 9 and k = 6, the guesses are 5, then 7, then 6. The successful guess is the third one.
Why it works
The current interval always contains k. A failed comparison removes only values known to lie on the wrong side and matches the stated strategy exactly. The interval shrinks after every failed guess until equality occurs, so the counter is precisely the number of guesses.
Watch out. Use 64-bit bounds. Remove the midpoint after a failed guess, and count the final successful guess.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long n, secret;
cin >> n >> secret;
long long lower = 1;
long long upper = n;
int guesses = 0;
while (lower <= upper) {
// This midpoint equals floor((lower + upper) / 2) without overflow.
long long middle = lower + (upper - lower) / 2;
guesses++;
if (middle == secret) {
break;
}
if (middle < secret) {
lower = middle + 1;
} else {
upper = middle - 1;
}
}
cout << guesses << '\n';
}