[LeetCode] 374. Guess Number Higher or Lower, Easy

1. 문제

• 정수 n이 주어질 때, 임의의 선택된 값을 찾아라.
• 사전 정의된 guess() 함수는 인자로 전달된 값에 따라 아래 결과를 반환한다.
  • 선택된 값보다 큰 경우, -1
  • 선택된 값보다 작은 경우, 1
  • 선택된 값을 찾은 경우, 0

2. 해결

/** 
 * Forward declaration of guess API.
 * @param {number} 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
 * var guess = function(num) {}
 */


function guessNumber(n: number): number {
    let left = 1, right = n;

    while(left <= right) {
        const mid = Math.floor((left + right)/ 2);
        const res = guess(mid);

        if(res === 1) left = mid + 1;
        else if(res === -1) right = mid - 1;
        else return mid;
    }

    return -1;
};

• 이진 탐색을 통해 찾으면 된다.
• 이진 탐색은 정렬된 상태에서 사용할 수 있고, 중간 값을 찾아 범위를 좁혀나가는 방식.