Двоичный поиск/деление пополам для чисел с плавающей запятой

64-битные числа с плавающей запятой IEEE-754 на самом деле являются 64-битными представлениями. Более того, за исключением значений NaN, нет никакой разницы между сравнением с плавающей запятой и сравнением целых чисел с положительными значениями. (То есть два битовых шаблона с неустановленным знаковым битом дадут один и тот же результат сравнения независимо от того, сравниваете ли вы их как int64_t или double, если только один из битовых шаблонов не является числом с плавающей запятой NaN-.)

Это означает, что вы можете найти число за 64 попытки, угадывая по одному биту за раз, даже если это число . Начните со сравнения числа с 0; если цель «меньше», то произведите предположения так же, как показано ниже, но отмените их перед предположением. (Поскольку числа с плавающей запятой IEEE-754 представляют собой знак/величину, вы можете инвертировать число, установив бит знака в 1. Или вы можете выполнить переинтерпретацию положительного битового шаблона, а затем отрицать результат с плавающей запятой.)

После этого угадывайте по одному биту за раз, начиная со старшего бита значения. Установите этот бит в 1, если число больше или равно предположению; установите этот бит в 0, если число меньше; и продолжайте со следующим битом, пока их больше не будет. Чтобы построить предположение, переинтерпретируйте битовую комбинацию как double.

Есть два предостережения:

1. Вы не можете отличить 0 от сравнительных тестов. Это означает, что если ваш оппонент хочет, чтобы вы различали их, он должен будет предоставить вам способ спросить о равенстве с 0, и вам придется использовать этот механизм после того, как вы, очевидно, установили, что число равно 0 ( что произойдет на 64-м предположении). Это добавит одно предположение, всего 65.

2. Если вы уверены, что цель не NaN, то других проблем нет. Если это может быть NaN, вам нужно быть осторожным при сравнении: все будет хорошо, если вы всегда будете спрашивать «X меньше этого предположения?», потому что сравнение NaN всегда будет возвращать false . Это означает, что после 11 последовательных ответов «нет» (не считая ответа на установление знака) вы обнаружите, что угадываете , при условии, что если число не меньше , то оно должно быть равно. Однако только в этом случае вам также необходимо явно проверить равенство, потому что это также будет ложным, если целью является NaN. Это не добавляет дополнительного предположения к счету, потому что это всегда происходит задолго до того, как будут израсходованы 64 предположения.

Тот же подход можно применить к числу с плавающей запятой. В худшем случае время выполнения составляет O (log n).

public class GuessComparer
{
    private float random;
    public GuessComparer() // generate a random float and keep it private
    {
        Random rnd = new Random();
        var buffer = new byte[4];
        rnd.NextBytes(buffer);
        random = BitConverter.ToSingle(buffer, 0);
    }
    public int CheckGuess(float quess) // answer whether number is high, lower or the same.
    {
        return random.CompareTo(quess);
    }
}
public class FloatFinder
{

    public static int Find(GuessComparer checker)
    {
        float guess = 0;
        int result = checker.CheckGuess(guess);
        int guesscount = 1;
        var high = float.MaxValue;
        var low = float.MinValue;
        while (result != 0)
        {
            if (result > 0) //random is higher than guess
                low = guess;
            else// random is lower than guess

                high = guess;

            guess = (high + low) / 2;
            guesscount++;
            result = checker.CheckGuess(guess);
        }
        Console.WriteLine("Found answer in {0}", guesscount);
        return guesscount;
    }

    public static void Find()
    {
        var checker = new GuessComparer();
        int guesses = Find(checker);
    }
}