LeetCode 374 - Guess Number Higher or Lower

https://www.hrwhisper.me/leetcode-guess-number-higher-lower/
https://leetcode.com/articles/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.

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }

http://www.bijishequ.com/detail/134759?p=66

Hint: 首先，因为target一定存在，所以就无需标准二分查找里的low>high返回-1的判断。另一个一直没注意的小细节是：计算mid要用low加上high和low差的一半的方法，否则就会溢出。之前做的二分查找相关的题，都没有大数据Case所以自己也没发现问题。这也给自己提了个醒：做完一定要看答案，反复学习更好的代码，发现自己的不足，甚至尝试更优的方案。否则做过多少遍，也都是没用的！！！

X. Ternary Search

• Time complexity : $O\big(\log_3 n \big)$. Ternary Search is used.

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

    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid1 = low + (high - low) / 3;
            int mid2 = high - (high - low) / 3;
            int res1 = guess(mid1);
            int res2 = guess(mid2);
            if (res1 == 0)
                return mid1;
            if (res2 == 0)
                return mid2;
            else if (res1 < 0)
                high = mid1 - 1;
            else if (res2 > 0)
                low = mid2 + 1;
            else {
                low = mid1 + 1;
                high = mid2 - 1;
            }
        }
        return -1;
    }

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

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

$$\begin{array}{cc}T\left(n\right)& =T(\frac{n}{2})+2,T\left(1\right)=1\\ T(\frac{n}{2})& =T(\frac{n}{2^2})+2\\ \\ \therefore T\left(n\right)& =T(\frac{n}{2^2})+2\times 2\\ & =T(\frac{n}{2^3})+3\times 2\\ & =\dots \\ & =T(\frac{n}{2^{{\log }_{2}n}})+2{\log }_{2}n\\ & =T\left(1\right)+2{\log }_{2}n\\ & =1+2{\log }_{2}n\end{array}$$

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

$$\begin{array}{cc}T\left(n\right)& =T(\frac{n}{3})+4,T\left(1\right)=1\\ T(\frac{n}{3})& =T(\frac{n}{3^2})+4\\ \\ \therefore T\left(n\right)& =T(\frac{n}{3^2})+2\times 4\\ & =T(\frac{n}{3^3})+3\times 4\\ & =\dots \\ & =T(\frac{n}{3^{{\log }_{3}n}})+4{\log }_{3}n\\ & =T\left(1\right)+4{\log }_{3}n\\ & =1+4{\log }_{3}n\end{array}$$

As shown above, the total comparisons in the worst case for ternary and binary search are $1 + 4 \log_3 n$ and $1 + 2 \log_2 n$ comparisons respectively. To determine which is larger, we can just look at the expression $2 \log_3 n$ and $\log_2 n$ . The expression $2 \log_3 n$ can be written as $\frac{2}{\log_2 3} \times \log_2 n$ . Since the value of $\frac{2}{\log_2 3}$ is greater than one, Ternary Search does more comparisons than Binary Search in the worst case.

    public int guessNumber(int n) {
        for (int i = 1; i < n; i++)
            if (guess(i) == 0)
                return i;
        return n;
    }