Guess Number Higher or Lower trong C++

Game đoán số: Player 1 chọn số trong [1, n]. Player 2 đoán, mỗi lần được báo "cao hơn", "thấp hơn" hoặc "trúng". Tìm số đã chọn dùng tìm kiếm nhị phân.

API: guess(num) trả về -1 (số bí mật thấp hơn), 1 (cao hơn), 0 (trúng).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int secret;
    int guess(int num) {
        if (secret > num) return 1;
        if (secret < num) return -1;
        return 0;
    }
public:
    Solution(int n) { secret = n; }
    int guessNumber(int n) {
        int l = 1, r = n;
        while (l <= r) {
            int m = l + (r - l) / 2;
            int g = guess(m);
            if (g == 0) return m;
            if (g == -1) r = m - 1;
            else l = m + 1;
        }
        return 0;
    }
};

int main() {
    Solution ob(5); // secret = 5
    cout << ob.guessNumber(10); // 5
    return 0;
}

Đầu vào / Đầu ra

Input: secret=5, n=10
Output: 5