[leetcode] 374. Guess Number Higher or Lower

링크

 

이진탐색이란 정렬된 배열에서 가운데 숫자를 고른 후, 찾으려던 숫자보다 작으면 가운데를 기준으로 앞의 절반 배열을 버리고 크면 가운데를 기준으로 뒤의 절반 배열을 버린 후 다시 가운데 숫자를 뽑아서 찾고자 하는 숫자를 찾아가는 탐색이다.

 

가운데 숫자를 고를 때는 배열 내 가장 작은 인덱스 + (가장 큰 인덱스 - 가장 작은 인덱스) / 2 로 찾는다.

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int mid = 1;
        int low = 1;
        int high = n;

        while(high >= low) {
            mid = low + (high - low) / 2;

            int result = guess(mid);
            if (result == 0) {
                break;
            }
            else if (result == -1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return mid;
    }
}

바보라서...짤 수 있었던 코드

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int mid = 1;
        BigInteger low = BigInteger.valueOf(1);
        BigInteger high = BigInteger.valueOf(n);

        while(high.compareTo(low) >= 0) {
            BigInteger temp1 = high;
            temp1 = temp1.add(low);
            temp1 = temp1.divide(BigInteger.valueOf(2));
            mid = temp1.intValue();

            int result = guess(mid);
            System.out.println(mid + ", " + high + " , " + low);
            if (result == 0) {
                break;
            }
            else if (result == -1) {
                high = BigInteger.valueOf(mid - 1);
            } else {
                low = BigInteger.valueOf(mid + 1);
            }
        }

        return mid;
    }
}