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