gpt4 book ai didi

c++ - 二进制搜索避免不可读的条目(列表中的漏洞)

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:20:38 25 4
gpt4 key购买 nike

我已经实现了二进制搜索功能,但我遇到了一个列表条目可能变得不可读的问题。它是用 C++ 实现的,但我只是使用一些伪代码来简化它。请不要关注不可读或字符串实现,它只是伪代码。重要的是列表中有不可读的条目,必须四处浏览。

int i = 0;
int imin = 0;
int imax = 99;
string search = "test";

while(imin <= imax)
{
i = imin + (imax - imin) / 2;
string text = vector.at(i);
if(text.isUnreadable())
{
continue;
}
if(compare(text, search) = 0)
{
break;
}
else if(compare(text, search) < 0)
{
imin = i + 1;
}
else if(compare(text, search) > 0)
{
imax = i - 1;
}
}

搜索本身运行良好,但我遇到的问题是如果文本不可读,如何避免无限循环。有人对此有耗时考验的方法吗?循环不应该只是在不可读时退出,而是应该绕过这个洞。

最佳答案

我在一个项目中有类似的任务 - 查找某些项目不可比较的序列。

我不确定这是最好的实现方式,在我的例子中它看起来像这样:

 int low = first_comparable(0,env);
int high = last_comparable(env.total() - 1,env);
while (low < high)
{
int mid = low + ((high - low) / 2);

int tmid = last_comparable(mid,env);
if( tmid < low )
{
tmid = first_comparable(mid,env);
if( tmid == high )
return high;
if( tmid > high )
return -1;
}
mid = tmid;
...
}

如果 vector.at(mid) 项是不可比较的,它会在其邻域中查找最接近的可比较对象。

first/last_comparable() 函数返回给定索引中第一个可比较元素的索引。方向不同。

  inline int first_comparable( int n, E& env)
{
int n_elements = env.total();
for( ; n < n_elements; ++n )
if( env.is_comparable(n) )
return n;
return n;
}

关于c++ - 二进制搜索避免不可读的条目(列表中的漏洞),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33350833/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com