Leetcode 374) Guess Number Higher or Lower

07 Sep 2021 in Algorithms

내 답안

/** 
 * 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);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        //1~n 까지 범위가 주어짐.
        int left=1;
        int right=n;
        while(left<=right){
            int mid= left+(right-left)/2;
            if(guess(mid)==0){
                return mid;
            }else if(guess(mid)==1){
                //target이 내 추측보다 높다. 
                left= mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
}

오답

• left+right 하면 overflow해서 오류난다!!!

/** 
 * 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);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        //1~n 까지 범위가 주어짐.
        int left=1;
        int right=n;
        while(left<=right){
            int mid= (left+right)/2;
            if(guess(mid)==0){
                return mid;
            }else if(guess(mid)==1){
                //target이 내 추측보다 높다. 
                left= mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
}

와! 공유해야지?

(left+right)/2 이렇게 안하고, left + (right-left)/2 하는 이유는, 32int범위가 overflow하지 않게 하기 위해서다.