374 Guess Number Higher or Lower

374. Guess Number Higher or Lower​
1. Question
We are playing the Guess Game. The game is as follows:
I pick a number from1ton. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined APIguess(int num)which returns 3 possible results (-1,1, or0):
1
-1 : My number is lower
2
 1 : My number is higher
3
 0 : Congrats! You got it!
Copied!
Example:
1
n = 10, I pick 6.
2
​
3
Return 6.
Copied!
2. Implementation
(1) Binary Search
1
/* The guess API is defined in the parent class GuessGame.
2
   @param num, your guess
3
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
4
      int guess(int num); */
5
​
6
public class Solution extends GuessGame {
7
    public int guessNumber(int n) {
8
        int start = 1, end = n, mid = 0;
9
​
10
        while (start <= end) {
11
            mid = start + (end - start) / 2;
12
            if (guess(mid) == -1) {
13
                end = mid - 1;
14
            }
15
            else if (guess(mid) == 1) {
16
                start = mid + 1;
17
            }
18
            else {
19
                return mid;
20
            }
21
        }
22
        return -1;
23
    }
24
}
Copied!
3. Time & Space Complexity
时间复杂度O(logn), 空间复杂度O(1)

367 Valid Perfect Square

410 Split Array Largest Sum

Last modified 2yr ago

Copy link

Contents

374. Guess Number Higher or Lower

1. Question

2. Implementation

3. Time & Space Complexity

374. Guess Number Higher or Lower​

1. Question

2. Implementation

3. Time & Space Complexity

374. Guess Number Higher or Lower