374. Guess Number Higher or Lower

题目：

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.

链接：

https://leetcode.com/problems/guess-number-higher-or-lower/#/description

3/17/2017

果然是简单题，但是要注意返回值的意义。

 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 lo = 1, hi = n;
 9         int mid;
10         int ret;
11         
12         while (lo <= hi) {
13             mid = lo + (hi - lo) / 2;
14             ret = guess(mid);
15             if (ret == 0) return mid;
16             else if (ret > 0) {
17                 lo = mid + 1;
18             } else {
19                 hi = mid - 1;
20             }
21         }
22         return 0;
23     }
24 }

官方解答里有更多内容，包括ternary search，以及与binary search的比较

https://leetcode.com/articles/guess-number-higher-or-lower/