Leetcode 0374 Guess Number Higher or Lower

Problem statement

https://leetcode.com/problems/guess-number-higher-or-lower/

Solution

Just simulate binary search with O(log_2 n) time complexity and O(1) space. We can also use ternary search with O(log_3 n) complexity.

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def guessNumber(self, n):
        beg, end = 1, n
        while beg <= end:
            mid = (beg + end)//2
            t = guess(mid)
            if t == 0: return mid
            if t == -1: end = mid - 1
            if t == 1:  beg = mid + 1