C++で数値の高低を推測する:二分探索を使った数当てゲームの解き方

問題概要

ここでは、いわゆる「数当てゲーム(Guess Game)」を考えます。このゲームのルールは以下のとおりです。

プレイヤー1が1からnまでの範囲からある1つの数を選びます。プレイヤー2は、その数が何であるかを推測しなければなりません。プレイヤー2の推測が外れるたびに、プレイヤー1は「選んだ数はもっと大きい」か「もっと小さい」かを教えてくれます。

この問題では、guess(num)という関数を利用できます。この関数は次の3つの値のいずれかを返します。

• -1:プレイヤー1が選んだ数は、numよりも小さい
• 1:プレイヤー1が選んだ数は、numよりも大きい
• 0:推測が的中した(数が一致した)

たとえば、入力が n = 10、pick = 5 の場合、出力は 5 になります。

解法アプローチ:二分探索

この問題は、二分探索(バイナリサーチ)を使うことで効率的に解けます。毎回の推測で候補となる範囲が半分に絞られていくため、線形探索(1つずつ順番に試す方法)よりもはるかに高速です。

具体的な手順は以下のとおりです。

1. 探索範囲の下限 l := 1、上限 r := n とします。
2. l <= r の間、次の処理を繰り返します。
   • 中央値 m := l + (r - l) / 2 を計算します。
   • guess(m) が 0 を返せば、m が答えなので m を返します。
   • guess(m) が -1 を返せば、答えは左半分にあるため、r := m - 1 とします。
   • それ以外(1が返った場合)は、答えは右半分にあるため、l := m + 1 とします。
3. ループが終了しても見つからなければ、0 を返します。

計算量

二分探索により、各ステップで探索範囲が半減するため、時間計算量は O(log n) となります。空間計算量は O(1) です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
    int number;
    int guess(int num){
        if(number > num)
            return 1;
        if(number < num)
            return -1;
        return 0;
    }
public:
    Solution(int n){
        number = n;
    }
    int guessNumber(int n) {
        int l=1,r=n,m;
        while(l<=r){
            m=l+(r-l)/2;
            if(guess(m)==0)
                return m;
            if(guess(m)==-1)
                r=m-1;
            else
                l=m+1;
        }
        return 0;
    }
};
main(){
    Solution ob(5); //pick = 5
    cout << (ob.guessNumber(10));
}

入力

5, 10

出力

5

コードのポイント

• m = l + (r - l) / 2 と書くことで、(l + r) / 2 のように直接足し算をする場合に発生しうるオーバーフローを防いでいます。これは競技プログラミングや実務において重要なテクニックです。
• Solutionクラスのコンストラクタで正解の数(pick)を保持し、guess() 関数がその数との大小関係を判定しています。
• whileループ内で条件に応じて探索範囲を狭めることで、最大でも log₂(n) 回程度の推測で正解にたどり着きます。

このように、数当てゲームのような「大小ヒントが得られる探索問題」では、二分探索が最適な戦略となります。ぜひ自分でも実装して、動作を確認してみてください。