Preface explains

Algorithm learning, daily brush problem record.

Subject to connect

Guess the number size

The subject content

The rules of the guessing game are as follows:

In each round, I’m going to pick a random number from 1 to N, and I’m going to ask you to guess which number I picked.

If you’re wrong, I’ll tell you whether the number you guessed is bigger or smaller than the number I picked.

Int guess(int Num) : int guess(int num) : int guess(int num);

-1: the number I pick is smaller than the number you guess

1: The number I pick is bigger than your guess

0: THE number I picked is the same as your guess. A: congratulations! You guessed it! pick == num

Returns the number I selected.

Example 1:

Type: n = 10, pick = 6

Output: 6

Example 2:

Type: n = 1, pick = 1

Output: 1.

Example 3:

Type: n = 2, pick = 1

Output: 1.

Example 4:

Type: n = 2, pick = 2

Output: 2

Tip:

1 <= n <= 2^31 – 1

1 <= pick <= n

The analysis process

So if you look at the problem, if you look in dichotomy, you take the middle value of 1 minus n, you call guess and you compare it to pick.

If guess is greater than 0, then pick > num, so pick is in the interval [mid + 1, right].

If the guess result is less than 0, then pick < num, the selected number is less than the guess, so the selected number is in the interval [left, mid-1].

Note: the guess function is reversed because pick is used as the reference point, rather than passing in the num argument.

So here’s the code:

/** * Forward declaration of guess API. * @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 * int guess(int num); */ Public class Solution extends GuessGame {public int guessNumber(int n) { Int left = 1, right = n; Int center = (left + right) / 2; Int result = guess(center); // Loop until guess is 0 while (result! = 0) {if (result > 0) {// If (result > 0) = 0, pick > num, left = center + 1; } else {// if < 0, pick < num, right = center-1; // if < 0, pick < num, right = center-1; } center = (left + right) / 2; Result = guess(center); } return center;} return center;} return center; }}Copy the code

However, after submitting the message, the runtime timed out:

What’s the reason? We can look at the range of n in the prompt:

1 <= n <= 2^31 – 1

In fact, if you put in 2^ 31-1 and 1, you’re already overrunning the integers in the first place, so you can imagine that if you add 2^ 31-1 to an intermediate index for binary search and divide by 2, 2^ 31-1 is already the maximum integer, and if you add another number, you’re definitely overrunning the integers, As a result, the intermediate index jumps during binary search, and finally leads to the timeout of the running time. We calculate the intermediate index as follows:

Int center = (left + right) / 2;Copy the code

This is where the error is. This may cause an integer overflow. We need to use another method to calculate the intermediate index.

Int center = left + (right-left) / 2; int center = left + (right-left) / 2;Copy the code

That way, there will be no integer overflow.

To solve the code

Therefore, we need to consider the problem of integer overflow. The solution code is as follows:

/** * Forward declaration of guess API. * @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 * int guess(int num); */ Public class Solution extends GuessGame {public int guessNumber(int n) { Int left = 1, right = n; Int center = left + (right-left) / 2; int center = left + (right-left) / 2; Int result = guess(center); // Loop until guess is 0 while (result! = 0) {if (result > 0) {// If (result > 0) = 0, pick > num, left = center + 1; } else {// if < 0, pick < num, right = center-1; // if < 0, pick < num, right = center-1; } center = left + (right-left) / 2; Result = guess(center); } return center;} return center;} return center; }}Copy the code

Submit the results

Execution time was 0ms, beating 100.00% of users in time, memory consumption was 35MB, beating 84.51% of users in space.

The original link

Guess the size of the number