Solution


Approach 1: Brute Force

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

Complexity Analysis

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


Algorithm

We can apply Binary Search to find the given number. We start with the mid number. 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 for numbers higher than itself.

Complexity Analysis

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


Algorithm

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 .

Complexity Analysis

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


Follow up

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.

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

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.

Analysis written by: @vinod23