Guess Number Higher or Lower

Problem

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.

Solution

/* 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); */

Binary Search: O(log_2 n) time

public class Solution {
    public int guessNumber(int n) {
        int start = 1, end = n;
        while (start < end) {
            int mid = start + (end - start) / 2; //avoid overflow 
            int guess = guess(mid);
            if (guess == 0) return mid;
            if (guess == 1) start = mid + 1;
            else end = mid - 1;
        }
        return start;
    }
}

Ternary Search: O(log_3 n) time

public class Solution {
    public int guessNumber(int n) {
        int start = 1, end = n;
        while (start < end) {
            int mid1 = start + (end - start) / 3;
            int mid2 = end - (end - start) / 3;
            int guess1 = guess(mid1), guess2 = guess(mid2);
            if (guess1 == 0) return mid1;
            if (guess2 == 0) return mid2;
            if (guess1 == -1) end = mid1 - 1;
            else if (guess2 == 1) start = mid2 + 1;
            else {
                start = mid1 + 1;
                end = mid2 - 1;
            }
        }
        return start;
    }
}

Analysis

A typical searching problem applied Binary Search and Ternary Search
Notice that in binary search, using mid = (start + end) / 2 might cause overflow
In ternary search, we get mid1 by start + (end - start) / 3
We get mid2 by end - (end - start) / 3
Then we update start and end based on the result of mid1 and mid2
Ternary Search is more time efficient ;)