374. Guess Number Higher or Lower

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {number}
 */

题目给我们一个数字 n，然后想要跟我们玩猜数字的游戏

我们每次可以调用内置的 guess 方法传入一个数字，这个方法会告诉我们这个数字猜中了或者大了小了

我们需要在最短的次数中猜中数字并返回

解题思路

我们可以用二分搜索的思路来找数字

我们需要 left 来确定当前的左边界、right 来确定当前的右边界

每次循环都猜 mid，mid = Math.floor((left + right) / 2)

如果当前猜的数字大了，我们更新 right、否则更新 left

Javascript

/** 
 * 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) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
    let left = 1
    let right = n
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        const res = guess(mid)
        if (res === 0) {
            return mid
        }
        if (res < 0) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
};

复杂度分析

时间

由于采用二分搜索，每次循环都会减少一半搜索量，所以是 O(logn)

空间

O(1)