# LeetCode 374: Guess Number Higher or Lower

## Problem Restatement

We are playing a number guessing game.

A hidden number `pick` has been chosen from:

```python
1 to n
```

We need to find `pick`.

We cannot read `pick` directly. Instead, we call a provided API:

```python
guess(num)
```

The API returns:

| Return value | Meaning |
|---:|---|
| `-1` | Our guess is too high, so `num > pick` |
| `1` | Our guess is too low, so `num < pick` |
| `0` | Our guess is correct, so `num == pick` |

Return the hidden number. The search range is `1 <= pick <= n`, and `n` can be as large as `2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Hidden value | `pick`, chosen from `1` to `n` |
| Output | The value of `pick` |
| API | `guess(num)` tells whether the guess is high, low, or correct |

Example function shape:

```python
def guessNumber(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 10
pick = 6
```

If we guess `5`, the API returns `1`, because `5` is too low.

If we guess `8`, the API returns `-1`, because `8` is too high.

If we guess `6`, the API returns `0`.

So the answer is:

```python
6
```

Example 2:

```python
n = 1
pick = 1
```

There is only one possible number, so the answer is:

```python
1
```

## First Thought: Linear Search

A simple solution is to try every number from `1` to `n`.

```python
class Solution:
    def guessNumber(self, n: int) -> int:
        for num in range(1, n + 1):
            if guess(num) == 0:
                return num
```

This is correct, but it can take `O(n)` calls to `guess`.

Since `n` may be very large, this is too slow.

## Key Insight

The API tells us which half of the search range can be discarded.

If we guess `mid`:

| API result | What we know | Next range |
|---:|---|---|
| `0` | `mid` is the answer | Stop |
| `-1` | `mid` is too high | Search left half |
| `1` | `mid` is too low | Search right half |

This is exactly binary search.

## Algorithm

Maintain a search range:

```python
left = 1
right = n
```

While `left <= right`:

1. Compute the middle value.
2. Call `guess(mid)`.
3. If the result is `0`, return `mid`.
4. If the result is `-1`, move `right` to `mid - 1`.
5. If the result is `1`, move `left` to `mid + 1`.

## Correctness

The hidden number starts inside the range `[1, n]`.

At each step, the algorithm guesses `mid`.

If `guess(mid) == 0`, then `mid` equals the hidden number, so returning it is correct.

If `guess(mid) == -1`, then `mid` is greater than the hidden number. Every number greater than or equal to `mid` can be discarded, so the hidden number remains in `[left, mid - 1]`.

If `guess(mid) == 1`, then `mid` is smaller than the hidden number. Every number less than or equal to `mid` can be discarded, so the hidden number remains in `[mid + 1, right]`.

Thus the search range always contains the hidden number until it is found. Since the range shrinks every iteration, the algorithm eventually returns the correct number.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` | Each guess halves the search range |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
# The guess API is already defined for you.
# def guess(num: int) -> int:
#     ...

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n

        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)

            if result == 0:
                return mid

            if result == -1:
                right = mid - 1
            else:
                left = mid + 1

        return -1
```

## Code Explanation

The search starts with the full range:

```python
left = 1
right = n
```

The midpoint is computed safely:

```python
mid = left + (right - left) // 2
```

In Python, overflow is not an issue. In fixed-width integer languages, this form avoids overflow.

Then we call the API:

```python
result = guess(mid)
```

If the result is `0`, we found the answer.

If the result is `-1`, our guess is too high:

```python
right = mid - 1
```

If the result is `1`, our guess is too low:

```python
left = mid + 1
```

The final `return -1` is only a safety fallback. Under the problem constraints, the answer always exists.

## Testing

LeetCode provides the `guess` API. For local testing, we can mock it with a closure.

```python
def make_solution(pick):
    def guess(num):
        if num > pick:
            return -1
        if num < pick:
            return 1
        return 0

    class Solution:
        def guessNumber(self, n: int) -> int:
            left = 1
            right = n

            while left <= right:
                mid = left + (right - left) // 2
                result = guess(mid)

                if result == 0:
                    return mid

                if result == -1:
                    right = mid - 1
                else:
                    left = mid + 1

            return -1

    return Solution()

def run_tests():
    assert make_solution(6).guessNumber(10) == 6
    assert make_solution(1).guessNumber(1) == 1
    assert make_solution(1).guessNumber(2) == 1
    assert make_solution(2).guessNumber(2) == 2
    assert make_solution(1702766719).guessNumber(2126753390) == 1702766719

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 10, pick = 6` | Standard example |
| `n = 1, pick = 1` | Smallest range |
| `pick` at left boundary | Checks left-side shrinking |
| `pick` at right boundary | Checks right-side shrinking |
| Large values | Confirms logarithmic search and safe midpoint |