基于二分查找实现optimal()方法寻找无符号整数函数最大值

你的代码存在的问题 #

• 变量类型错误：定义域是0到2^64-1，unsigned int通常是32位（最大值仅为2^32-1），无法容纳2^64-1，必须使用uint64_t（需包含头文件<stdint.h>）。另外你写的2e32是浮点数，转整数会丢失精度，正确的2^64-1应该用宏UINT64_MAX或直接写0xFFFFFFFFFFFFFFFFULL。
• 单调判断逻辑错误：你仅通过首尾相邻点判断单调性，但逻辑表述有误，且即使判断正确，也完全没处理核心的"先增后减"场景，直接返回0显然不对。
• 数值范围错误：2e32远大于2^64（约1.8e19），属于低级的数值概念错误。

正确实现思路 #

已知函数是严格递增、严格递减、先增后减（单峰），我们可以通过二分查找直接定位峰值，这个逻辑会自动覆盖所有三种情况：

1. 初始化左右边界low = 0，high = UINT64_MAX。
2. 循环直到low == high：
   • 计算中间点mid = low + (high - low)/2（避免无符号整数加法溢出）。
   • 比较func(mid)和func(mid+1)：
     • 如果func(mid) < func(mid+1)，说明峰值在mid+1到high区间，将low设为mid+1。
     • 如果func(mid) > func(mid+1)，说明峰值在low到mid区间，将high设为mid。
3. 循环结束时，low（等于high）就是最大值对应的索引。

这个逻辑天然适配单调场景：

• 严格递增时，每次都会触发func(mid) < func(mid+1)，low最终会移动到UINT64_MAX。
• 严格递减时，第一次比较就会触发func(0) > func(1)，high直接设为0，循环结束。

修正后的代码 #

#include <stdint.h>

uint64_t optimal() {
    uint64_t low = 0;
    uint64_t high = UINT64_MAX;

    while (low < high) {
        // 安全计算中间值，避免加法溢出
        uint64_t mid = low + (high - low) / 2;
        double val_mid = func(mid);
        double val_next = func(mid + 1);

        if (val_mid < val_next) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low;
}

关键细节说明 #

• 溢出规避：无符号整数的加法溢出是未定义行为吗？不，无符号整数溢出会按模2^n处理，但直接(low+high)/2会得到错误的中间值，用low + (high-low)/2能安全计算出正确的中点。
• 减少函数调用：将func(mid)和func(mid+1)的结果缓存，避免重复调用（假设func是开销较大的操作）。
• 类型匹配：所有索引变量用uint64_t，确保覆盖整个0~2^64-1的定义域。

内容的提问来源于stack exchange，提问作者Ian Burns