Guess Number Game

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):

Example

n = 10, I pick 4 (but you don't know)

Return 4. Correct !

注意计算中间节点的方法 (start+end)/2 和 start +(end-start)/2

前者对于Integer.MAX_VALUE溢出后者ok

 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     /**
 8      * @param n an integer
 9      * @return the number you guess
10      */
11     public int guessNumber(int n) {
12         // Write your code here
13         int start = 1;
14         int end = n;
15         while(start<end){
16             int mid = start+(end-start)/2;
17             int res = guess(mid);
18             if(res==0) return mid;
19             else if(res==1) start = mid+1;
20             else end = mid-1;
21         }
22         return start;
23     }
24 }