
Binary Search, Easy
Question
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. 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 API guess(int num) which returns 3 possible results (-1, 1, or 0):
1 2 3
|
-1 : My number is lower 1 : My number is higher 0 : Congrats! You got it!
|
Example:
1 2 3
|
n = 10, I pick 6. Return 6.
|
Answer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
@param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class extends GuessGame { public int guessNumber(int n) { int start = 1, end = n; while(start < end){ int mid = i + (j - i) / 2; if(guess(mid)==0) return mid; else if(guess(mid)==1) start = mid + 1; else end = mid; } return start; } }
|
Time complexity: O(logn)
Space complexity: O(1)
1
|
int mid = (start + end) / 2;
|
it will become infinite loop
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
1063376695 -552418605 787167393 -690523256 718115067 -725049419 700851986 -733680959 696536216 -735838844 695457273 -736378316 695187537 -736513184 695120103 -736546901 695103245 -736555330 695099030 ...
|
due to integer overflow (when j+i becomes a negative number), you get into an infinite loop.
近期评论