UVA 10077-为什么它是二进制搜索？

Question

我正在努力提高CP。我遇到了这个问题-Link。当我想到一个幼稚的BFS解决方案O（2 ^ N）时，它显然给了我一个TLE。

string bfs(int t1,int t2)
{
    queue<pair<VII,string>> st;
    st.push({{0,1,1,2,1,1},"L"});
    st.push({{1,1,2,1,1,0},"R"});
    while(!st.empty())
    {
        VII u=st.front().first;
        string v=st.front().second;
        st.pop();
        //cout<<u[2]<<' '<<u[3]<<endl;
        if(u[2]==t1 && u[3]==t2)
        return v;
        st.push({{u[0],u[1],u[0]+u[2],u[1]+u[3],u[2],u[3]},v+"L"});
        st.push({{u[2],u[3],u[2]+u[4],u[3]+u[5],u[4],u[5]},v+"R"});
    }
    return "";
}

以上是我能想到的代码。我知道有二进制搜索解决方案，但是我不明白如何划分搜索空间。如果有人可以向我解释其背后的直觉，那就太好了。谢谢！

Answer 1

您正在尝试在无限间隔lo=(0,1) hi=(1,0)中找到目标编号。如PDF所述，您可以通过执行mid = (lo[0]+hi[0])/(lo[1]+hi[1])来找到间隔的中点。决定左移还是右移取决于mid和目标编号的比较。如果向左走，则发出L并开始在lo=lo hi=mid间隔内搜索。如果向右走，则发出R并在lo=mid hi=hi间隔内开始搜索。重复直到mid == target。

这是Python中的快速解决方案：

from fractions import Fraction
def walk(lo, hi, tgt):
    mid = (lo[0] + hi[0], lo[1] + hi[1])
    fmid = Fraction(mid[0], mid[1])
    if tgt == fmid:
        return
    if tgt < fmid:
        yield 'L'
        yield from walk(lo, mid, tgt)
    else:
        yield 'R'
        yield from walk(mid, hi, tgt)

print(list(walk((0,1), (1,0), Fraction(878, 323))))