Loading...
墨滴

Shinkai005

2021/12/12  阅读:31  主题:红绯

【leetcode】374.猜数字游戏(二分搜索)

【leetcode】374.猜数字游戏(二分搜索)

题目描述

image-20211212132538130
image-20211212132538130

题目思路

  • 二分搜索的应用
  • 调用guess函数,来判断中间元素是不是目标值

个人题解

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


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

var guessNumber = function (n{
    /**
     从数组的中间元素开始,如果中间元素正好是目标值,则搜索过程结束
     如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找
     */

    let low = 1;
    let high = n;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid);
        if (res === 0) {
            return mid;
        } else if (res === 1) {
            low = mid + 1
        } else if (res === -1) {
            high = mid - 1;
        } else {
            throw new Error('内置函数guess错误');
        }
    }
};

时间复杂度(time complexity)

O(logn)

空间复杂度(space complexity)

O(1)

Shinkai005

2021/12/12  阅读:31  主题:红绯

作者介绍

Shinkai005