为什么代码在进行二分搜索猜测时没有反映实际的数学行为？

Question

我决定创建一个小程序，使用我认为的二分搜索来查找给定范围内的数字。据我所知，该代码运行良好。当我想要创建一个数学函数来预测猜测给定数字所需的平均猜测次数时，问题就出现了，而且直观地讲，该函数是：

log2(x) + 1

但是，当对代码进行实验测试时，像

1e12

这样的大数的结果更类似于以下公式：

log2(x) - 1

此外，该公式可能不正确，因为我对此表示怀疑。无论如何，这是代码，以防您发现计算有任何问题：

use rand::Rng;
use std::io;
use std::cmp::Ordering;
use std::time::Instant;

fn read_input() -> i64 {
    println!("Insert the range of the number [1 - <input>]: ");

    let mut max_range_str = String::new();

    io::stdin()
        .read_line(&mut max_range_str)
        .expect("Couldn't read the line");

    let max_range = max_range_str
        .trim()
        .parse()
        .expect("Couldn't convert to int");

    println!("");
    
    max_range
}

fn create_secret_number(max_range: i64) -> i64 {
    rand::thread_rng().gen_range(1..=max_range)
}

fn main() {
    let max_range = read_input();
    let mut loop_count = 0;
    let mut sum_of_guesses = 0;
    loop {
        let start_time = Instant::now();
        let secret_number = create_secret_number(max_range);

        let mut iterations = 0;
        let mut ceiling = max_range;
        let mut floor = 0;
        let mut guess = max_range / 2;

        loop {
            iterations += 1;
            match guess.cmp(&secret_number) {
                Ordering::Greater => ceiling = guess,
                Ordering::Less => floor = guess,
                Ordering::Equal => {
                    let elapsed_time = start_time.elapsed();
                    println!("The correct number was {}", secret_number);
                    println!("You win after {} iterations in {:?} seconds \n", iterations, elapsed_time);
                    sum_of_guesses += iterations;
                    break;
                }
            }
            guess = (ceiling + floor) / 2;
        }

        loop_count += 1;
        let average_guesses = sum_of_guesses / loop_count;
        println!("Average guess is now: {}", average_guesses);
    }
}

Answer 1

我正在自己学习 Rust [免责声明，你不应该受到我的编码约定的启发]。

让我们从一个简单的算法开始。从

1

到

2

的某个幂的范围开始。 我假设所有范围都是 2 的幂。在此假设下，您的代码将猜测值置于第 1 半的最大值上。因此，如果猜测值低于秘密数字，那么你就猜对了一半。然后你可以将这一半分成自己的两半并重复该过程：

            1..8
    1..4←?→         5..8
1..2    3..4    5..6    7..8

我修改了你的代码，修复了一些错误，并删除了控制台打印，这太慢了，你最好一次迭代超过一百万次尝试，而不是不断迭代并等待，直到最终达到一百万次：

use rand::Rng;
use std::io;

fn read_input() -> i64 {
    println!("Insert the range of the number [1 - <input>]: ");

    let mut max_range_str = String::new();

    io::stdin()
        .read_line(&mut max_range_str)
        .expect("Couldn't read the line");

    let max_range = max_range_str
        .trim()
        .parse()
        .expect("Couldn't convert to int");

    println!("");
    
    max_range
}

fn create_secret_number(max_range: i64) -> i64 {
    rand::thread_rng().gen_range(1..=max_range)
}

fn main() {
    let max_range = read_input();
    let mut sum_of_guesses = 0;
    let tries = 100000;
    for _ in 1..=tries { // was infinite
        let secret_number = create_secret_number(max_range);

        let mut ceiling = max_range;
        let mut floor = 1;  // was 0, but range starts at 1!
        
        for iterations in 0..max_range { // ensure it doesn't hang but break early
            if floor == ceiling {
                sum_of_guesses += iterations;
                break;
            }
            // position guess at upper bound of first pair
            let guess = (floor + ceiling) / 2;
            
            if guess > secret_number {
                // the pair guessed correctly
                ceiling = guess;
            } else {
                // the pair guessed wrongly - so the other is the right one
                // +1 to move from upper bound of 1st pair to lower bound of 2nd
                floor = guess + 1;
            }
        }
    }
    let average_guesses = sum_of_guesses as f64 / tries as f64; // was int div!
    println!("Average guess is: {}", average_guesses);
}

请记住，我可以将

max_range

中的

for iterations in 0..max_range

替换为最大值的 log2，但随后我会假设我要证明的内容……也许很明显，结果是 log2 猜测的平均值（例如 7 为范围为 128），因为这是细分数（128, 64, 32, 16, 8, 4, 2；迭代的最后一步不计算在内，因为没有什么可以猜测）。

但是，您的代码有很小的机会提前中断：

• 1..128 - 1/128 提前突破的机会
• 1..64（或 65..128）- 1/64 提前突破的机会
• 1..32（或...）- 1/32 机会
• 1..16 - 1/16
• 1/8
• 1/4
• 1/2

正如您所看到的，范围越大，提前突破的可能性就越接近 100%。除了，正如我已经说过的，说你可以从最里面的对（例如 1..2）提前打破是不公平的，因为无论如何这将是最后的猜测。因此，考虑到粗体的假设，您提前突破的机会接近 50%。

如果由于某些错误的原因，您认为提前突破意味着将

sum_of_guesses

减少

1

，那么范围越大，实际平均值就越接近 log2max - 0.5。然而，也许同样明显的是，你越早打破，你就越能避免猜测：

• 1/4 机会保存 1 个猜测 = 平均保存 1/4 个猜测
• 1/8 机会保存 2 个猜测 = 2/8 = 平均保存 1/4 个猜测
• 1/16 * 3 = 3/16
• 1/32 * 4 = 4/32 = 1/8

依此类推，接近一个猜测已保存。