81 lines
1.4 KiB
Markdown
81 lines
1.4 KiB
Markdown
---
|
|
layout: page
|
|
title: Guess Number Higher or Lower
|
|
last_solved:
|
|
category: binary search
|
|
leetcode_url: https://leetcode.com/problems/guess-number-higher-or-lower
|
|
status: Attempted
|
|
---
|
|
|
|
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'll tell you whether the number is higher or lower.
|
|
|
|
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
|
|
|
|
-1 : My number is lower
|
|
1 : My number is higher
|
|
0 : Congrats! You got it!
|
|
Example :
|
|
|
|
Input: n = 10, pick = 6
|
|
Output: 6
|
|
|
|
```
|
|
|
|
Solution
|
|
----------
|
|
|
|
Simplist binary search ever
|
|
|
|
{% highlight python %}
|
|
|
|
def guessNumber(self, n: int) -> int:
|
|
|
|
low, high = 1, n
|
|
|
|
while low<=high:
|
|
|
|
mid = (low+high)//2
|
|
|
|
if guess(mid)==0:
|
|
return mid
|
|
elif guess(mid)==-1:
|
|
high = mid-1
|
|
else:
|
|
low = mid+1
|
|
|
|
return None
|
|
|
|
{% endhighlight %}
|
|
|
|
__________
|
|
|
|
{% highlight python %}
|
|
|
|
def guessNumber(self, n: int) -> int:
|
|
|
|
left, right = 1, n
|
|
|
|
while left<right:
|
|
|
|
mid = (left+right)//2
|
|
|
|
result = guess(mid)
|
|
|
|
if result<=0:
|
|
right = mid # target is lower, so ignore everything on the right
|
|
else:
|
|
left = mid+1
|
|
|
|
return left
|
|
|
|
{% endhighlight %}
|
|
|
|
![image1]() |