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

Question

我已经实现了二进制搜索功能，但我遇到了一个列表条目可能变得不可读的问题。它是用 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;
    }
}

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

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