TwentyQuestions.java

/*************************************************************************
 *  Compilation:  javac TwentyQuestions.java
 *  Execution:    java TwentyQuestions
 *  Dependencies  StdIn.java
 *
 *  Think of an integer between 0 and 1000000.
 *  Truthfully answer 'yes' or 'no' to each question I ask.
 *
 *  Q1: Is your number <= 500000?
 *  yes
 *  Q2: Is your number <= 250000?
 *  yes
 *  Q3: Is your number <= 125000?
 *  yes
 *  Q4: Is your number <= 62500? 
 *  no
 *  Q5: Is your number <= 93750?
 *  yes
 *  Q6: Is your number <= 78125?
 *  no
 *  Q7: Is your number <= 85938?
 *  yes
 *  Q8: Is your number <= 82032?
 *  yes
 *  Q9: Is your number <= 80079?
 *  no
 *  Q10: Is your number <= 81056?
 *  yes
 *  Q11: Is your number <= 80568?
 *  yes
 *  Q12: Is your number <= 80324?
 *  no
 *  Q13: Is your number <= 80446?
 *  yes
 *  Q14: Is your number <= 80385?
 *  yes
 *  Q15: Is your number <= 80355?
 *  yes
 *  Q16: Is your number <= 80340?
 *  no
 *  Q17: Is your number <= 80348?
 *  yes
 *  Q18: Is your number <= 80344?
 *  yes
 *  Q19: Is your number <= 80342?
 *  yes
 *  Q20: Is your number <= 80341? 
 *  no
 *
 *  Your integer is 80342.
 *
 *************************************************************************/

public class TwentyQuestions { 

    public static void main(String[] args) { 
        int lo = 0, hi = 1000000;
        System.out.println("Think of an integer between " + lo + " and " + hi + ".");
        System.out.println("Truthfully answer 'yes' or 'no' to each question I ask.");
        System.out.println();

        for (int i = 1; lo < hi; i++) {
            // invariant:  number must be in the interval [lo, hi]
            int mid = (lo + hi) / 2;
            System.out.print("Q" + i + ": ");
            System.out.println("Is your number <= " + mid + "?");
            boolean response = StdIn.readBoolean();
            if (response) hi = mid;
            else          lo = mid + 1;
        }

        System.out.println("Your integer is " + lo + ".");
        System.out.println();
    }

}