374. Guess Number Higher or Lower

Description

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 <= 2³¹ - 1
• 1 <= pick <= n

Submitted Code

# 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):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        min = 1
        max = n

        while min <= max:
            mid = (min + max) // 2

            if guess(mid) == 0:
                return mid
            elif guess(mid) == 1:
                min = mid + 1
            else:
                max = mid - 1

Runtime: 11 ms | Beats 87.17%
Memory: 12.46 MB | Beats 49.53%

이진 탐색을 사용한 방법이다.

Other Solutions

1st

from bisect import bisect_left

class Solution:
    def guessNumber(self, n):
        return bisect_left(range(n), 0, key=lambda m: -guess(m))

time complexity: 𝑂(log𝑛)
space complexity: 𝑂(1)

파이썬 내장함수 bisect_left으로도 이진 탐색 알고리즘을 사용할 수 있다. 이 함수는 오름차순으로 정렬된 리스트에서 pick을 삽입할 수 있는 가장 좌측의 인덱스를 찾는다. range(n)로 0부터 n-1까지 숫자를 생성하고, key값은 -guess(m)가 된다. -를 붙이는 이유는 정답이 리턴값보다 더 작은 숫자일 경우 -1이 반환되고 더 큰 숫자일 경우 1이 반환되는데, 이를 반전시켜서 정렬된 리스트로 만드는 것이다.

n = 10
pick = 6
range(10) → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

left   right   mid    guess(m)    -guess(m)    비교결과
0      10      5       1          -1           -1 < 0 → right
6      10      8      -1           1            1 > 0 → left
6       8      7      -1           1            1 > 0 → left
6       7      6       0           0           0 == 0 → return        

return 6