# Guess Number Higher or Lower - LeetCode Problem

# Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the [Guess Number Higher or Lower problem](https://leetcode.com/problems/guess-number-higher-or-lower/).

You are playing the Guess Game with your friend. In this game, your friend thinks of a number between `1` and `n`, and you have to guess which number they have chosen. Each time you guess a number, your friend will tell you whether the number is higher, lower, or equal to their chosen number. You call a pre-defined API `guess(int num)` which returns 3 possible results:

* `-1`: The number I guessed is higher than the number your friend has chosen.
    
* `1`: The number I guessed is lower than the number your friend has chosen.
    
* `0`: Congratulations! You've guessed the correct number!
    

That's it! Now, let's dive into the solution.

## Solution

We can use a binary search approach to solve this problem. Since the numbers are sorted in ascending order, we can compare the middle element of the range with the target number. Based on the result of the `guess()` function, we can either narrow down the search to the lower half or the upper half of the range.

Here's the Python code for our solution:

```python
def guessNumber(n: int) -> int:
    left, right = 1, n
    
    while left <= right:
        mid = (left + right) // 2
        
        result = guess(mid)
        
        if result == 0:
            return mid
        elif result == -1:
            right = mid - 1
        else:
            left = mid + 1
```

Let's go through this code step-by-step.

1. We initialize two pointers `left` and `right` to the beginning and end of the range, respectively.
    

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

1. We use a `while` loop to repeatedly divide the range in half and narrow down the search space.
    

```python
while left <= right:
```

Note that we're using `<=` instead of `<` in the loop condition. This is because we want to continue the loop until the range is of size 1 (i.e., `left == right`), which may be the target number.

1. We calculate the middle index of the current search space.
    

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

1. We call the `guess()` function with the middle element of the range and store the result.
    

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

1. Based on the result of the `guess()` function, we either narrow down the search to the lower half or the upper half of the range.
    

```python
if result == 0:
    return mid
elif result == -1:
    right = mid - 1
else:
    left = mid + 1
```

If `result == 0`, then we know that we've guessed the correct number, so we return `mid`. If `result == -1`, then we know that the target number is in the lower half of the range, so we set `right = mid - 1`. Otherwise, we know that the target number is in the upper half of the range, so we set `left = mid + 1`.

## Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

### Time Complexity

Our solution uses binary search to guess the target number. Since we're dividing the search space in half at each step, the time complexity of our solution is `O(log n)`, where `n` is the size of the range.

### Space Complexity

Our solution uses a constant amount of extra space to keep track of the pointers `left`, `right`, and `mid`, as well as the result of the `guess()` function. Therefore, the space complexity of our solution is `O(1)`.

## Conclusion

And there you have it! We've successfully tackled the Guess Number Higher or Lower problem. I hope you found this blog post helpful and informative. Happy Coding! 😎