This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

374. Guess the number size – LeetCode (leetcode-cn.com)

The rules of the guessing game are as follows:

  • Every round of the game, I take it from1 到 nPick a number at random. Guess which number you picked.
  • If you’re wrong, I’ll tell you if your guess is bigger or smaller than my pick.

You can get the guess result by calling a predefined interface int guess(int num), which returns three possible values (-1, 1 or 0) :

-1: I picked a smaller number than you guessed pick < num 1: I picked a larger number than you guessed pick > num 0: I picked the same number as you guessed. A: congratulations! You guessed it! pick == num

Returns the number I selected.

The sample a

Input: n = 10, pick = 6 Output: 6Copy the code

Example 2

Input: n = 1, pick = 1 Output: 1Copy the code

Example 3

Input: n = 2, pick = 1 Output: 1Copy the code

Example 4

Input: n = 2, pick = 2 Output: 2Copy the code

Tip:

  • 1 <= n <= 2^31 - 1
  • 1 <= pick <= n

Thought analysis

Binary search

This should be a typical binary search, our interval is [1..n], and guess(x) = 1 means the right interval is large.

AC code

class Solution {
/** 
 * The API guess is defined in the parent class.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * fun guess(num:Int):Int {}
 */

class Solution:GuessGame() {
    override fun guessNumber(n:Int):Int {
        // If the median is strictly less than the target number, then the left interval must not be a solution
        var left = 0
        var right = n
        while (left < right) {
            val mid = (left + right) ushr 1
            if (1 == guess(mid)) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}

Copy the code

conclusion

Typical binary search, you can try to use different binary search formula to write different solutions.

reference

Guess the size – Guess the size – LeetCode (leetcode-cn.com)

374. Guess Number Higher or Lower – Guess Number size – LeetCode (leetcode-cn.com)