бинарный поиск не доходит до конца

Question

import java.util.Scanner;

public class GuessingGame {

private Scanner reader;

public GuessingGame() {
    // use only this scanner, othervise the tests do not work
    this.reader = new Scanner(System.in);
}

public void play(int lowerLimit, int upperLimit) {
    instructions(lowerLimit, upperLimit);
    boolean isAboveAverage;
    int counter = -1;

    while (counter < howManyTimesHalvable(upperLimit - lowerLimit)) {
        isAboveAverage = isGreaterThan(average(lowerLimit, upperLimit));
        if (upperLimit == lowerLimit) {
            break;
        }
        if (isAboveAverage) {
            lowerLimit = average(lowerLimit, upperLimit);
        } else {
            upperLimit = average(lowerLimit, upperLimit);
        }
        counter++;
    }

    System.out.println("your number is " + upperLimit);
}

// implement here the methods isGreaterThan and average
public boolean isGreaterThan(int number) {
    boolean isGreater = false;
    boolean isCorrectAnswerGiven = false;

    while (!isCorrectAnswerGiven) {
        System.out.println("Is your number greater than " + (number) + "? (y/n)");
        String answer = reader.nextLine();

        if (answer.equals("yes") || answer.equals("y")) {
            isGreater = true;
            isCorrectAnswerGiven = true;
        } else if (answer.equals("no") || answer.equals("n")) {
            isCorrectAnswerGiven = true;
        }
    }

    return isGreater;
}

public int average(int upperLimit, int lowerLimit) {
    return (upperLimit + lowerLimit) / 2;
}

public int average2(int firstNumber, int secondNumber) {
    double res = (firstNumber + secondNumber) / 2.0;
    Math.round(res);
    //System.out.println(res);
    return (int) res;
}

public void instructions(int lowerLimit, int upperLimit) {
    int maxQuestions = howManyTimesHalvable(upperLimit - lowerLimit);

    System.out.println("Think of a number between " + lowerLimit + "..." + upperLimit + ".");

    System.out.println("I promise you that I can guess the number you are thinking with " + maxQuestions + " questions.");
    System.out.println("");
    System.out.println("Next I'll present you a series of questions. Answer them honestly.");
    System.out.println("");
}

// a helper method:
public static int howManyTimesHalvable(int number) {
    // we create a base two logarithm  of the given value

    // Below we swap the base number to base two logarithms!
    return (int) (Math.log(number) / Math.log(2)) + 1;
 }
}

У меня проблемы с отладкой этого кода. В этом классе я должен реализовать простой ИИ, который угадывает число на основе вашего ответа на вопрос «ваш номер больше, чем» + число. Мои проблемы. код никогда не достигает конца заданного диапазона (поэтому, с диапазоном от 1 до 10, он никогда не угадывает 1 или 10) и b. это не останавливается во времени. Java часто повторяет вопрос несколько раз, но программа должна сказать ответ, как только она сможет это знать.

Моя ошибка, очевидно, заключается в методе play (я включил весь класс для полноты), я просто не знаю, где. Моя программа работает, поэтому опечатка или программная ошибка маловероятны. Я должен сделать что-то не так в моей логике, но я не знаю что. Кто-нибудь знает, где лежит ошибка?

Answer 1

Есть некоторые проблемы с вашей логикой:

• Вы вычисляете howManyTimesHalvable на каждой итерации. Это не имеет смысла, учитывая увеличение counter. Последнее возможное значение для него всегда равно 1, что может быть намного ниже, чем текущее значение counter.
• Вы проверяете, совпадают ли верхний и нижний значения сразу после задания вопроса, не обновляя эти значения. Просто переместите его в конец цикла.
• Последнее, что вам нужно увеличить среднее значение на 1 при обновлении lowerLimit. Если ответ «Ваш номер больше X» - «да», то новый lowerLimit не может быть X.

Исправленный метод:

public void play(int lowerLimit, int upperLimit) {
    instructions(lowerLimit, upperLimit);
    boolean isAboveAverage;
    int counter = howManyTimesHalvable(upperLimit - lowerLimit);
    while (counter > 0) {
        isAboveAverage = isGreaterThan(average(lowerLimit, upperLimit));
        if (isAboveAverage) {
            lowerLimit = average(lowerLimit, upperLimit)+1;
        } else {
            upperLimit = average(lowerLimit, upperLimit);
        }
        if (upperLimit == lowerLimit) {
            break;
        }
        counter--;
    }
    System.out.println("your number is " + upperLimit);
}