# LeetCode Easy 374. Guess Number Higher or Lower

tags: leetcode

問題

• Explore
• Problems

我々は推測ゲームをしている. ゲームは次のようである.

私が$1$から$n$の数を1つ選ぶ. 私がどの数を選んだかを推測しなければならない.

間違って推測するごとに, その数が高いか低いかを教える.

予め定義された3つの可能性(-1, 1, もしくは0)を返すAPIguess(int num)を呼び出しなさい

-1 : 私の数の方が小さい

1 : 私の数の方が大きい

0 : おめでとう! 正解!

アイデア

$1$から$n$の範囲の数を当てるゲームで, 推測した数の大小から探し出します

単調性があるので二分探索が使えると考えられます

解法1(二分探索)

• 探索する範囲の左端と右端を決めます
• mid = left + (right - left) / 2;と定義して, ここからguessAPIの結果に応じて分岐させます
  • 結果がー1のときは私の数の方が小さいので右端をmid - 1にして左側を探索します
  • 結果が1のときは私の数の方が大きいので左端をmid + 1にして右側を探索します
  • 結果が0のときは数を当てているのでこの値を返します

計算量

• 時間計算量
  • 二分探索なので$O(\log n)$
• 空間計算量
  • 必要と成る変数は定数個なので$O(n)$

C++

ところでなのですが, LeetCodeは関数の終わりに出力を書かないとコンパイラがエラーを吐きます

なので最後にreturn -1;という無意味なコードを書く必要があるのです...

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
  int guessNumber(int n) {
    int left = 1, right = n;
    int res;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      int guess_res = guess(mid);
      switch(guess_res) {
        case -1:
          right = mid - 1;
          break;
        case 1:
          left = mid + 1;
          break;
        default:
          res = mid;
          return res;
      }
    }
    return -1;
  }
};

解法2(三分探索)

三分探索(Ternary Search)はその名の通り範囲を三分割して行う探索です

下の図のように探索範囲を三分割して, mid1, mid2の位置の値と探索する値から分岐をします

• mid1, mid2の位置にある値が探索する値であればそれを返します
• そうでなければ値に応じて探索する範囲を変える

計算量

• 時間計算量
  • 毎回3等分しているので$O(\log_{3}n)$
• 空間計算量
  • $O(n)$

C++

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
  int guessNumber(int n) {
    int left = 1, right = n;
    while (left <= right) {
      int mid1 = left + (right - left) / 3;
      int mid2 = right - (right - left) / 3;
      int res1 = guess(mid1);
      int res2 = guess(mid2);
      if (res1 == 0)
        return mid1;
      if (res2 == 0)
        return mid2;
      else if (res1 == -1)
        right = mid1 - 1;
      else if (res2 == 1)
        left = mid2 + 1;
      else {
        left = mid1 + 1;
        right = mid2 - 1;
      }
    }
    return -1;
  }
};