Угадай число, зная только, предложенное число меньше или больше?

Question

Мне нужно угадать число.Я могу только видеть, является ли число, которое я предлагаю, ниже или выше.Производительность очень важна, поэтому я подумал о следующем алгоритме:

Скажем, число, которое я пытаюсь угадать, равно 600.

• Я начинаю счисло 1000 (или для еще более высокой производительности, средний результат предыдущих чисел).

• Затем я проверяю, является ли 1000 выше или ниже 600. Это выше.

• Затем я делю число на 2 (чтобы теперь оно составляло 500), и проверяю, меньше или больше 600. Оно меньше.

• Затем я нахожу разницу и делю ее на 2 следующим образом, чтобы получить новое число: ((1000 - 500) / 2).Результат равен 750. Затем я проверяю это число.

И т. Д.

Это лучший подход?Есть ли более разумный способ сделать это?В моем случае каждое предположение занимает примерно 500 миллисекунд, и мне нужно угадать довольно много чисел за минимально возможное время.

Я могу приблизительно предположить, что средний результат предыдущих догадок близок к предстоящемучисла тоже, так что есть образец, который я могу использовать для своего собственного преимущества.

Answer 1

да binary search - самый эффективный способ сделать это.Binary Search это то, что вы описали.Для числа от 1 до N Binary Search выполняется за O(log(n)) время.

Так вот алгоритм поиска числа от 1-N

int a = 1, b = n, guess = average of previous answers;

while(guess is wrong) {

    if(guess lower than answer) {a = guess;}
    else if(guess higher than answer) {b = guess;}

    guess = (a+b)/2;

} //Go back to while

Answer 2

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

Точно так же, как вы используете"среднее"результат предыдущих догадок "зависит от вас;Было бы предложено сместить результаты к этому среднему значению, но вам нужно будет проанализировать, насколько показательны предыдущие результаты, чтобы выработать наилучший подход.Не просто используйте среднее значение: используйте полное распределение.

Например, если все результаты были в диапазоне 600-700 (даже если гипотетический диапазон составляет до 1000) со средним значением 670, вы можете начать с 670, но если он скажет "угадайте выше", вы, вероятно, захотите выбрать значение между 670 и 700 в качестве следующего предположения, а не 835 (что весьма вероятно 1012 * выше реального результата).

Я предлагаю вам зарегистрировать все результаты предыдущих запросов, чтобы затем использовать их в качестве тестовых данных для альтернативных подходов.

Answer 3

Да, бинарный поиск (ваш алгоритм) здесь правильный. Однако в стандартном бинарном поиске отсутствует одна вещь:

Для бинарного поиска вам обычно нужно знать максимум и минимум, между которыми вы ищете. В случае, если вы этого не знаете, вы должны итеративно найти максимум в начале, например:

• Начните с нуля
• если оно больше, чем искомое число, ваш максимум равен нулю, и вы должны найти минимум
• если оно меньше, чем искомое число, ваш минимум равен нулю, а вы должны найти максимум
• Вы можете искать свой максимум / минимум, начиная с 1 или -1 и всегда умножая на два, пока не найдете число, которое больше / меньше

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

Answer 4

Как правило, бинарный поиск, начинающийся в средней точке диапазона, является оптимальной стратегией.Однако у вас есть дополнительная конкретная информация, которая может сделать эту стратегию неоптимальной.Это критически зависит от того, что именно означает «близко к среднему значению предыдущих результатов».

Если числа близки к предыдущему среднему значению, то деление на 2 на втором этапе не является оптимальным.

Пример: предыдущие номера 630, 650, 620, 660. Вы начинаете с 640.

Ваш номер на самом деле ближе.Представьте, что это 634.

Число ниже.Если на втором шаге вы делите на 2, вы получаете 320, таким образом теряя какое-либо преимущество относительно предыдущих средних чисел.

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

Answer 5

int a = 1, b = n+1, guess = average of previous answers;

while(guess is wrong) {

    if(guess lower than answer) {a = guess;}
    else if(guess higher than answer) {b = guess;}

    guess = (a+b)/2;

} //Go back to while

Вы должны добавить +1 к n, иначе вы никогда не сможете получить n, так как это int.

Answer 6

Стандартный двоичный поиск от 0 до N (N - это заданное число) даст вам ответ за время logN.

Answer 7

Знаете ли вы диапазон возможных значений?Если да, всегда начинайте с середины и делайте то, что вы описываете.