每日算法 — 使用java实现猜大小：二分搜索与信息熵最优猜测策略

游戏简介与算法背景

猜大小是一款经典的数字猜测游戏：系统随机生成一个范围内的整数，玩家通过不断猜测来获取”大了”或”小了”的反馈，直至猜中目标数字。表面上看这只是运气游戏，但背后蕴含着丰富的算法思想——二分搜索能以最少次数保证猜中，而信息熵理论则揭示了最优策略的数学本质。

核心算法设计

1. 二分搜索策略

对于范围 [1, N] 的数字，二分搜索每次将候选区间折半，时间复杂度为 O(log N)，是最优的确定性策略。核心思想是始终猜测当前区间的中间值，从而最大化每次获得的信息量。

2. 信息熵分析

信息熵 H = -Σ p(x) * log₂p(x) 度量了系统的不确定性。对于均匀分布的 N 个数字，熵为 log₂N。每次二分搜索将熵减少约 1 比特，因此最少需要 ⌈log₂N⌉ 次猜测才能消除全部不确定性。

3. 最优策略扩展：非均匀分布

当目标数字服从非均匀分布时，简单的二分搜索不再最优。此时应采用加权中位数策略，使得左右子区间的概率质量尽量均衡，从而最小化期望猜测次数。

Java 完整实现

import java.util.Random;
import java.util.Scanner;

/**
 * 猜大小游戏 — 二分搜索与信息熵最优策略实现
 * 
 * 核心算法：
 * 1. 标准二分搜索：O(log N) 时间复杂度
 * 2. 加权二分搜索：针对非均匀分布的最优策略
 * 3. 信息熵计算：量化每次猜测的信息增益
 */
public class GuessNumberGame {

    private final int minBound;
    private final int maxBound;
    private final int target;
    private int guessCount;

    public GuessNumberGame(int min, int max) {
        this.minBound = min;
        this.maxBound = max;
        this.target = new Random().nextInt(max - min + 1) + min;
        this.guessCount = 0;
    }

    /**
     * 标准二分搜索策略
     * 每次选择区间中点，保证最少最坏情况猜测次数
     */
    public int binarySearchGuess() {
        int left = minBound;
        int right = maxBound;

        while (left <= right) {
            // 使用无溢出风险的中点计算
            int mid = left + (right - left) / 2;
            guessCount++;

            System.out.printf("猜测 #%d: %d%n", guessCount, mid);

            if (mid == target) {
                System.out.println("猜中了！");
                return guessCount;
            } else if (mid < target) {
                System.out.println("太小了！");
                left = mid + 1;
            } else {
                System.out.println("太大了！");
                right = mid - 1;
            }
        }

        return -1; // 理论上不会到达此处
    }

    /**
     * 加权二分搜索 — 针对非均匀分布的最优策略
     * @param probabilities 每个数字的出现概率数组，索引对应数字-minBound
     */
    public int weightedBinarySearch(double[] probabilities) {
        int left = minBound;
        int right = maxBound;

        while (left <= right) {
            // 计算当前区间内左右两部分的累积概率
            double leftProb = 0, rightProb = 0;
            int totalLen = right - left + 1;

            // 寻找使左右概率质量最均衡的分割点
            int bestSplit = left;
            double minDiff = Double.MAX_VALUE;

            for (int split = left; split <= right; split++) {
                leftProb = 0;
                rightProb = 0;

                for (int i = left; i <= right; i++) {
                    int idx = i - minBound;
                    if (idx >= 0 && idx < probabilities.length) {
                        if (i <= split) leftProb += probabilities[idx];
                        else rightProb += probabilities[idx];
                    }
                }

                double diff = Math.abs(leftProb - rightProb);
                if (diff < minDiff) {
                    minDiff = diff;
                    bestSplit = split;
                }
            }

            guessCount++;
            System.out.printf("加权猜测 #%d: %d (左概率=%.3f, 右概率=%.3f)%n", 
                guessCount, bestSplit, leftProb, rightProb);

            if (bestSplit == target) {
                System.out.println("猜中了！");
                return guessCount;
            } else if (bestSplit < target) {
                System.out.println("太小了！");
                left = bestSplit + 1;
            } else {
                System.out.println("太大了！");
                right = bestSplit - 1;
            }
        }

        return -1;
    }

    /**
     * 计算信息熵
     * H = -Σ p(x) * log₂(p(x))
     */
    public static double calculateEntropy(double[] probabilities) {
        double entropy = 0.0;
        for (double p : probabilities) {
            if (p > 0) {
                entropy -= p * (Math.log(p) / Math.log(2));
            }
        }
        return entropy;
    }

    /**
     * 计算均匀分布下的理论最优猜测次数
     */
    public static int theoreticalOptimalGuesses(int range) {
        return (int) Math.ceil(Math.log(range) / Math.log(2));
    }

    /**
     * 交互式游戏入口
     */
    public void playInteractive() {
        Scanner scanner = new Scanner(System.in);
        System.out.printf("已生成一个 %d 到 %d 之间的数字，请猜测！%n", minBound, maxBound);
        System.out.printf("理论最优次数：%d 次%n", theoreticalOptimalGuesses(maxBound - minBound + 1));

        int left = minBound;
        int right = maxBound;

        while (true) {
            System.out.printf("当前范围 [%d, %d]，请输入猜测：", left, right);
            int guess = scanner.nextInt();
            guessCount++;

            if (guess == target) {
                System.out.printf("恭喜！你在 %d 次内猜中了！%n", guessCount);
                break;
            } else if (guess < target) {
                System.out.println("太小了！");
                left = Math.max(left, guess + 1);
            } else {
                System.out.println("太大了！");
                right = Math.min(right, guess - 1);
            }
        }

        scanner.close();
    }

    public static void main(String[] args) {
        // 演示1：标准二分搜索
        System.out.println("=== 演示1：标准二分搜索 (范围 1-1000) ===");
        GuessNumberGame game1 = new GuessNumberGame(1, 1000);
        int count1 = game1.binarySearchGuess();
        System.out.printf("总共猜测 %d 次，理论最优 %d 次%n%n", 
            count1, theoreticalOptimalGuesses(1000));

        // 演示2：非均匀分布的加权搜索
        System.out.println("=== 演示2：加权二分搜索 (范围 1-100) ===");
        GuessNumberGame game2 = new GuessNumberGame(1, 100);
        double[] probs = new double[100];
        // 模拟正态分布：中间数字概率更高
        for (int i = 0; i < 100; i++) {
            double x = (i - 49.5) / 20.0;
            probs[i] = Math.exp(-x * x / 2);
        }
        // 归一化
        double sum = 0;
        for (double p : probs) sum += p;
        for (int i = 0; i < 100; i++) probs[i] /= sum;

        System.out.printf("分布熵：%.4f bits%n", calculateEntropy(probs));
        int count2 = game2.weightedBinarySearch(probs);
        System.out.printf("加权策略总共猜测 %d 次%n", count2);
    }
}

算法复杂度分析

扩展思考

1. 三分搜索的适用场景：当比较代价不对称时（例如”接近”有三种反馈），三分搜索可能更优。
2. 噪声环境下的猜测：若反馈有概率出错，需要结合贝叶斯更新和冗余验证策略。
3. 范围动态扩展：当上限未知时，可采用指数搜索先确定范围，再执行二分搜索，整体复杂度仍为 O(log N)。

总结

猜大小游戏完美展示了二分搜索的优雅与高效。通过信息熵的视角，我们理解了为什么二分搜索是最优策略——它每次都将不确定性精确减半。而加权二分搜索则将这一思想推广到非均匀场景，体现了算法设计中”根据问题结构调整策略”的核心思想。