# Guess Number Higher or Lower
**Difficulty:** EASY
[External](https://leetcode.com/problems/guess-number-higher-or-lower)
Canonical: https://scaleengineer.com/dsa/problems/guess-number-higher-or-lower
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## 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 will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API `int guess(int num)`, which returns three possible results:

* `-1`: Your guess is higher than the number I picked (i.e. `num > pick`).
* `1`: Your guess is lower than the number I picked (i.e. `num < pick`).
* `0`: your guess is equal to the number I picked (i.e. `num == pick`).

Return _the number that I picked_.

**Example 1:**

**Input:** n = 10, pick = 6
**Output:** 6

**Example 2:**

**Input:** n = 1, pick = 1
**Output:** 1

**Example 3:**

**Input:** n = 2, pick = 1
**Output:** 1

**Constraints:**

* `1 <= n <= 231 - 1`
* `1 <= pick <= n`

# Approaches
## Linear Search
This approach involves checking every number sequentially from 1 up to n. We call the `guess()` API for each number until we find the correct one.
**Time:** O(n) - In the worst-case scenario, we might have to iterate through all the numbers from 1 to n. · **Space:** O(1) - We only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient for large values of `n`.; Will result in a 'Time Limit Exceeded' error on most coding platforms due to the `n` constraint being up to `2^31 - 1`.
### Explanation
We start by guessing the number 1. We then call the `guess(1)` API. If it returns 0, we've found the number. If not, we proceed to guess 2, then 3, and so on, until we reach n. This method is straightforward but very slow, as it might require up to `n` calls to the `guess()` API in the worst case.

```java
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 * 		      1 if num is lower than the picked number
 *               0 if num is equal to the picked number
 * public int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        for (int i = 1; i <= n; i++) {
            if (guess(i) == 0) {
                return i;
            }
        }
        return -1; // Should not be reached based on problem constraints
    }
}
```
### Algorithm
- 1. Iterate through numbers from `i = 1` to `n`.
- 2. For each number `i`, call the `guess(i)` API.
- 3. If `guess(i)` returns `0`, it means `i` is the correct number. Return `i`.
- 4. If the loop finishes, it means the number was not found (this case is not possible according to the problem constraints).

## Binary Search
This is the optimal approach. It works by maintaining a range of possible numbers `[low, high]` and repeatedly guessing the middle number. Based on the API's feedback, we eliminate half of the range in each step, drastically reducing the search time.
**Time:** O(log n) - With each guess, we eliminate half of the remaining search space, leading to logarithmic time complexity. · **Space:** O(1) - We only use a constant amount of extra space for pointers and the middle value.
**Pros:** Extremely efficient and optimal for this problem.; Handles large values of `n` easily within time limits.
**Cons:** Slightly more complex to conceptualize than a linear scan, but it's a fundamental algorithm.
### Explanation
We initialize two pointers, `low` to 1 and `high` to `n`, which define our search space. In each step of the loop, we calculate the middle point `mid`. It's calculated as `low + (high - low) / 2` to avoid potential integer overflow when `low` and `high` are large. We then call `guess(mid)`.
- If `guess(mid)` returns 0, we've found the number and can return `mid`.
- If `guess(mid)` returns -1 (our guess is too high), we know the picked number must be in the lower half, so we update `high = mid - 1`.
- If `guess(mid)` returns 1 (our guess is too low), the picked number must be in the upper half, so we update `low = mid + 1`.
We repeat this process until `low` is no longer less than or equal to `high`, at which point we will have found the number.

```java
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 * 		      1 if num is lower than the picked number
 *               0 if num is equal to the picked number
 * public int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            // Using (low + high) / 2 might cause overflow for large n
            int mid = low + (high - low) / 2; 
            int result = guess(mid);
            if (result == 0) {
                return mid;
            } else if (result == -1) {
                // My guess is higher than the picked number
                high = mid - 1;
            } else {
                // My guess is lower than the picked number
                low = mid + 1;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- 1. Initialize two pointers, `low = 1` and `high = n`.
- 2. Loop as long as `low <= high`.
- 3. Calculate the middle index: `mid = low + (high - low) / 2`.
- 4. Call the `guess(mid)` API.
- 5. If the result is `0`, return `mid`.
- 6. If the result is `-1` (guess is too high), it means the target is in the lower half, so update `high = mid - 1`.
- 7. If the result is `1` (guess is too low), it means the target is in the upper half, so update `low = mid + 1`.

# Solutions
### CSharp

```csharp
/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is higher than the picked number * 1 if num is lower than the picked number * otherwise return 0 * int guess(int num); */ public class Solution : GuessGame { public int GuessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### Java

```java
/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ public class Solution extends GuessGame { public int guessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### CPP

```cpp
/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ class Solution { public: int guessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } };
```

### Python

```python
# The guess API is already defined for you. # @param num, your guess # @return -1 if num is higher than the picked number # 1 if num is lower than the picked number # otherwise return 0 # def guess(num: int) -> int: class Solution : def guessNumber ( self , n : int ) -> int : return bisect . bisect ( range ( 1 , n + 1 ), 0 , key = lambda x : - guess ( x ))
```