二分探索-leetcode Guess Number Higher or Lower

二分探索

検索対象と探索範囲の真ん中の値を比較して，探索範囲をだんだん半分に狭め、見つけるアルゴリズムです。

問題文

私たちは推測ゲームをしています。ゲームは次のとおりです。

1 から n までの数字を選択します。私が選んだ数字を当ててください。

あなたが間違った推測をするたびに、私が選んだ数字があなたの推測より高いか低いかを教えます。

事前定義された API intgues(int num) を呼び出すと、次の 3 つの可能な結果が返されます。

-1: あなたの推測は私が選んだ数字よりも大きいです (つまり、num > pick)。
1: あなたの推測は私が選んだ数字よりも小さいです (つまり、num < pick)。
0: あなたの推測は私が選んだ数字と同じです (つまり、num == pick)。
私が選んだ番号を返します。

コード java

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start=1;
        int mid = 0;
      while(start <= n){
      //探索範囲の真ん中の値①を取得
          mid =start + (n-start)/2;
     //①が検索対象と一致しているか確認
          int ans = guess(mid);
    //一致していた場合、①を返す
          if(ans ==0) return mid;
    //①が検索対象より小さい場合、start地点を右にずらす
          else if(ans==1) start = mid + 1;
    //①が検索対象より大きい場合、n地点を左にずらす
          else n = mid-1;
      }
      return -1;
    }
}

実行時間:0ms
メモリー:40.2MB