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 "";
}

以上是我能够想出的代码。我知道有二进制搜索解决方案，但我无法理解如何划分搜索 space。如果有人能向我解释这背后的直觉，那就太好了。谢谢！

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))))

UVA 10077 - 为什么是二分查找？

UVA 10077 - Why is it Binary search?

c++

algorithm

binary-search