(Leet Code c++)Cuess 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 3 possible results:

• -1: The number I picked is lower than your guess (i.e. pick < num).
• 1: The number I picked is higher than your guess (i.e. pick > num).
• 0: The number I picked is equal to your guess (i.e. pick == num).

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

Example 4:

Input: n = 2, pick = 2 Output: 2

 

Constraints:

• 1 <= n <= 231 - 1
• 1 <= pick <= n

guess() 함수를 이용해 숫자를 예측해야 한다.

n의 범위가 1 ~ 2^31 - 1이기 때문에 이진 탐색을 활용.

 

front = 1, back = n으로 시작.

while문으로 이진 탐색 시작.

mid 는 front와 back의 중간 값이다.

 

mid를 guess() 함수에 전달하여 리턴값에 따라 front와 back 값을 조절한다.

guess(mid)가 -1이면 예측값이 정답값보다 크다는 뜻이기 때문에 back = mid - 1로 설정.

guess(mid)가 1이면 예측값이 정답값보다 작기 때문에 front = mid + 1로 설정.

guess(mid)가 0이라면 정답이기 때문에 mid값을 리턴한다.

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int front = 1, back = n;
        
        while(front <= back){
            int mid = front + (back - front) / 2;
            
            if(guess(mid) < 0){
                back = mid - 1;
            }
            else if(guess(mid) > 0){
                front = mid + 1;
            }
            else{
                return mid;
            }
        }
        
        return front;
    }
};