c++ - 二进制搜索到实数函数的上限

标签 c++ binary-search

给定一个整数 X,我需要找到最大整数 N,使得 N*log(N) <= X。

我正在使用二进制搜索来计算答案,但我认为在某些情况下循环会无限运行。

这是我的二进制搜索函数:

int f(int X)
{
    int lo=1, hi=time;
    while(lo < hi)
    {
        int mid = lo + hi;
        mid/=2;
        if(mid*log2((double)mid) == X)
        {
            return mid;
        }
        if(mid*log2((double)mid) <= X)
        {
            hi = mid;
        }
        else lo=mid;
    }
    return lo;
}

我的方法正确吗?如果是,我的代码中的错误是什么?如果不是,正确的做法是什么?

最佳答案

考虑如果 hi - lo == 1 会发生什么。在这种情况下,mid 等于 lo,因此 lo = mid 是空操作,您可能会陷入无限循环。

关于c++ - 二进制搜索到实数函数的上限,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26699689/

相关文章:

使用自定义函数的Java二元搜索

C++ 转换不工作

c++ - For 循环打印一个额外的逗号

c++ - 对 C++ 字符串的二进制搜索不起作用

algorithm - 如何在一个谎言模型中进行二分查找?

algorithm - 为了更快速地搜索,难道不应该在进行二分搜索之前对数据应用合并排序,还是直接跳到线性搜索?

arrays - 未排序数组二分查找的时间复杂度

c++ - 缺少析构函数声明

c++ - 使用基于此标志的条件语句是否比添加更多代码行更有效?

c++ - 使用 strtoll 从二进制字符串转换为 int?