[LeetCode] 374. Guess Number Higher or Lower

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

Use binary search to locate the target number.

We can optimize the process by narrowing the window down as small as possible before start the binary search.

Time Complexity = O ( Log N )

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = n, 1
        
        while guess(left) == -1:
            # left = left // 2
            left >>= 1 
        
        while guess(right) == 1:
            # right = right * 2
            right <<= 1 
        
        while left <= right:
            # mid = left + (right - left) // 2
            mid = left + ((right - left) >> 1)
            
            tmp = guess(mid)
            if tmp == 0: return mid
            if tmp == 1: left = mid + 1
            if tmp == -1: right = mid - 1
        
        return left