LeetCode: 374. Guess Number Higher or Lower

問題の要約

• 1 から n の範囲で、予め１つだけ選択された数字を当てる
• 用意されたAPI=guess(int n) に数値を指定すると、数値は n より大きい/小さいのヒント or 正解が返却される

問題

問題へのリンク

回答　その１　全探索

• まずはブルート・フォースを作成。
• 1～n を 総当たりで guess関数に問い合わせる。

class Solution {
public:
    int guessNumber(int n) {
        int i=0;
        for(;i<n;i++){
            if(guess(i)==0) break;
        }
        return i;
    }
};

時間計算量は O(N)

提出すると当然 Time Limit Exceeded。14/25 テストケースまでPassした所で拒否されました。

回答　その２　二分探索

• 次に「二分探索」で計算量を削減しました。
• 「二分探索」は英語で「バイナリーサーチ」

class Solution {
public:
    int guessNumber(int n) {
        long int low=1, high=n, ans=1;
        while(low<=high){
            int mid=(int)((low+high)/2);
            int ans=guess(mid);
            if(ans==0) return mid;
            if(ans==1) low=mid+1;
            else high=mid-1;
        }
        return -1;
    }
};

時間計算量は O(logN)

提出すると、Accepted。Runtime=0 ms、Memory=8.1 MB。Runtime=0msって 1ms以下ってことですかね。

※ low+high が int型の範囲を越えるので、long int型で計算してからint型にキャストしました。
　 int mid=low+(high-low)/2; の方が int型の範囲を超えず、良かったかもしれません。