[LeetCode] 374. Guess Number Higher or Lower

374. Guess Number Higher or Lower

 

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.

 

 

Answer

 

class Solution:
    def guessNumber(self, n: int) -> int:
        low, high = 1, n
        while low <= high:
            mid = (low + high) // 2 
            result = guess(mid)
            
            if result == -1:
                high = mid ㅁ- 1
            elif result == 1:
                low = mid + 1
            else:
                return mid

 

How Binary Search Works

 

Precondition : 

The input list or range must be sorted

 

Divide and Conquer : 

Start with the entire search range

Calculate the middle point of the range.

Compare the target value with the middleelement.

 

Dicision:

If the target is smaller than the middlel element, eliminate the upper half of the range.

If the target is larger. eliminate the lower half.

If the target is equal to the middle element, return it.

 

So

in Each Loop

until low exceeds high:

- Calculate the middle point : mid = (low + high) // 2

- Check

    If the value at mid is equal to the target, return mid

    If the value at mid is greater thatn the target, move high to mid - 1

    If the value at mid is less than the target, move low to mid + 1