题目
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 : My number is lower 1 : My number is higher 0 : Congrats! You got it!Example:
n = 10, I pick 6. Return 6. 思路： 要求：使用对数的时间复杂度来完成本题目。我从1-n中选出一个数，然后对方来猜，如果对方猜不中，就告诉对方我的数是比他的数高还是低；注意guess函数是返回1,0，-1的值。使用二分查找法注意溢出的情况，使用 mid=(j-i)/2+i;而不使用mid=(j+i)/2,数字太大就会导致溢出 代码： /* The guess API is defined in the parent class GuessGame. @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 Solution extends GuessGame { public int guessNumber(int n) { int i=1; int j=n; int mid=0; //使用二分法查找 while(i<=j){ //求中间数 mid=(j-i)/2+i; //guess(int num)是用来返回目标值比你猜的这个数是高了还是低了 int val=guess(mid); //-1表示我的数字比你猜的数字要小 if(val==-1) j=mid-1; else if(val==1) //+1表示我的数字比你猜的数字要大 i=mid+1; else return mid; } return -1; } } 原题地址