## 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.


b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

We check every number from 1 to n-1 and pass it to the function. The number\nfor which a 0 is returned is the required answer.

\n

Java

\n
/* The guess API is defined in the parent class GuessGame.\n   @param num, your guess\n   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n      int guess(int num); */\n\npublic class Solution extends GuessGame {\n    public int guessNumber(int n) {\n        for (int i = 1; i < n; i++)\n            if (guess(i) == 0)\n                return i;\n        return n;\n    }\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : . We scan all the numbers from 1 to n.
• \n
• Space complexity : . No extra space is used.
• \n
\n
\n

#### Approach #2 Binary Search [Accepted]

\n

Algorithm

\n

We can apply Binary Search to find the given number. We start with the mid\nnumber. We pass that number to the function. If it returns a -1, it implies that the guessed number is larger than the required one. Thus, we use Binary Search for numbers lower than itself. Similarly, if it returns a 1, we use Binary Search\n for numbers higher than itself.

\n

Java

\n
/* The guess API is defined in the parent class GuessGame.\n   @param num, your guess\n   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n      int guess(int num); */\n\npublic class Solution extends GuessGame {\n    public int guessNumber(int n) {\n        int low = 1;\n        int high = n;\n        while (low <= high) {\n            int mid = low + (high - low) / 2;\n            int res = guess(mid);\n            if (res == 0)\n                return mid;\n            else if (res < 0)\n                high = mid - 1;\n            else\n                low = mid + 1;\n        }\n        return -1;\n    }\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : . Binary Search is used.
• \n
• Space complexity : . No extra space is used.
• \n
\n
\n

#### Approach #3 Ternary Search [Accepted]

\n

Algorithm

\n

In Binary Search, we choose the middle element as the pivot in splitting. In Ternary Search, we choose two pivots (say and ) such that the given range is divided into three equal parts. If the required number is less than then we apply ternary search on the left segment of . If lies between and , we apply ternary search between and . Otherwise we will search in the segment right to .

\n

Java

\n
/* The guess API is defined in the parent class GuessGame.\n   @param num, your guess\n   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n      int guess(int num); */\n\npublic class Solution extends GuessGame {\n    public int guessNumber(int n) {\n        int low = 1;\n        int high = n;\n        while (low <= high) {\n            int mid1 = low + (high - low) / 3;\n            int mid2 = high - (high - low) / 3;\n            int res1 = guess(mid1);\n            int res2 = guess(mid2);\n            if (res1 == 0)\n                return mid1;\n            if (res2 == 0)\n                return mid2;\n            else if (res1 < 0)\n                high = mid1 - 1;\n            else if (res2 > 0)\n                low = mid2 + 1;\n            else {\n                low = mid1 + 1;\n                high = mid2 - 1;\n            }\n        }\n        return -1;\n    }\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : . Ternary Search is used.
• \n
• Space complexity : . No extra space is used.
• \n
\n
\n

\n

It seems that ternary search is able to terminate earlier compared to binary search. But why is binary search more widely used?

\n\n

Ternary Search is worse than Binary Search. The following outlines the recursive formula to count comparisons of Binary Search in the worst case.

\n

\n\n

\n

The following outlines the recursive formula to count comparisons of Ternary Search in the worst case.

\n

\n\n

\n

As shown above, the total comparisons in the worst case for ternary and binary search are and comparisons respectively. To determine which is larger, we can just look at the expression and . The expression can be written as . Since the value of is greater than one, Ternary Search does more comparisons than Binary Search in the worst case.

\n

Analysis written by: @vinod23

\n
'