c++ - 如何使用一些关于范围的额外信息来加速二进制搜索

Question

我有一个游戏，是按以下方式玩的:

• 游戏开始时显示我在 <h>:<m>:<s>:<ms> 中的时间格式
• 接下来我猜测小于或等于之前打印的那个，然后输入。

• 游戏根据我的时间显示以下其中一项

  白金 金子 石头

• 从第 2 步开始重复。

这基本上就像一场比赛，时间是比赛的结束时间，我获得最佳(最低)时间的白金和最差(更大)时间的石头。请注意游戏给出的开始时间是Stone所需的最大时间.

我需要得到我能得到的最长时间Platinum .

所以我实现了一个二进制搜索算法，它将所需时间值所在的时间间隔减半。简单地:

low = mid + 1; // if i get platinum 
high = mid - 1; // otherwise

完整代码如下:

#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>


using namespace std;

class times
{
public:
int h,m,s,ms;
int mili;

times ()
{
    h = m=s=ms =0;
    mili = 0;
}


times(int a,int b,int c,int d)
{
    h = a,m=b,s=c,ms=d;
    make();
}


void bake( ) //do reverse of make() for given mili
{
    long int x = mili;
    ms = x%1000;
    x /= 1000;
    s = x%60;
    x/= 60;
    m = x%60;
    x /= 60;

}


void make()  // calc total mili based on cur val of h,m,s and ms
{
    mili = ms;
    mili += s*1000 + m*60*1000 + h*3600*1000;
}


};

int main()
{
int h,m,s,msl;
bool flag;
string str;
    scanf("%d:%d:%d:%d",&h,&m,&s,&msl);

    times mid(h,m,s,msl);
    int low=0,high;
    high = mid.mili;

    while( low < high )
    {
        mid.mili = (high+low)/2;
        mid.bake();
        printf("%d:%02d:%02d:%03d" , mid.h , mid.m,mid.s,mid.ms );
        fflush(stdout); //FLUSH

        cin>>str; // the relic

        if(str=="PLATINUM") // we have more time than req
            {
                low = mid.mili+1;
                flag = true;
            }
        else
            {
                high = mid.mili-1;
                flag = false;
            }


    }
    if(!flag)
        {

            mid.mili = high;
            mid.bake();
            printf("PLATINUM: %d:%02d:%02d:%03d" ,mid.h , mid.m,mid.s,mid.ms);
        }
    else
        {

           mid.mili = low;
            mid.bake();
            printf("PLATINUM: %d:%02d:%02d:%03d" ,mid.h , mid.m,mid.s,mid.ms);
        }

return 0;
}

但这似乎太慢了，我相信它可以以更好的方式完成，因为我认为我没有利用 Gold 的事实必须出现在 Platinum 之间和 Stone .

或者一般来说，如果我大致知道我离所需值有多远，我该如何改进二分搜索？

作为 Stone得离Platinum远一点比Gold是。

Answer 1

如果你不知道边界的分布，就好像你对你的问题一无所知。此外，由于获得“石头”或“金子”没有惩罚，您可以忘记这两者之间的界限，将整个设置视为“白金”——“非白金”。

同样，如果不知道这个单一边界在哪里，您将一无所获。这里的“想法”是指统计分布(--不同于均匀分布，因为这将导致通常的二进制半间隔搜索)。如果你有这样的分布，你可能不会通过简单地将当前间隔减半来继续，而是总是在其平均值点处进行切割。在这两种情况下，无论有没有信息，二分搜索应该给你最少的平均试验次数。

此外，如果考虑对“石头”(比如 penalty=2)和“金子”(比如 penalty=1)进行惩罚的版本，并且任务也是在解决问题时得到尽可能少的惩罚，这让我想起了鸡蛋掉落谜题的通用版本，see Wikipedia .