374. Guess Number Higher or Lower

leetcode easy

#csharp#easy#leetcode#search

Task

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).

1: Ваше предположение меньше загаданного числа (т.е. num < pick).

0: Ваше предположение равно загаданному числу (т.е. num == pick).

Верните загаданное число.

Пример:

Input: n = 10, pick = 6

Output: 6

C# solution

matched/original

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

Java solution

matched/original

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

JavaScript solution

matched/original

var guessNumber = function(n) {
    let low = 1, high = n;
    while (low <= high) {
        let mid = low + Math.floor((high - low) / 2);
        let res = guess(mid);
        if (res === 0) {
            return mid;
        } else if (res < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
};

Python solution

matched/original

class Solution:
    def guessNumber(self, n: int) -> int:
        low, high = 1, n
        while low <= high:
            mid = low + (high - low) // 2
            res = guess(mid)
            if res == 0:
                return mid
            elif res < 0:
                high = mid - 1
            else:
                low = mid + 1
        return -1

Go solution

matched/original

package main

func guessNumber(n int) int {
    low, high := 1, n
    for low <= high {
        mid := low + (high - low) / 2
        res := guess(mid)
        if res == 0 {
            return mid
        } else if res < 0 {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

Explanation

Algorithm

Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного.

Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.

😎