二进制搜索避免不可读的条目（列表中的漏洞）

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

the problem I have is how to avoid getting an endless loop if the text is unreadable.

似乎 continue 应该改为 break，这样您就可以跳出循环。您可能想要设置一个标志或其他东西来指示循环后面的任何代码的错误。

另一种选择是抛出异常。

真的，除了你正在做的事情，你几乎应该做任何事情。目前，当您阅读这些 'unreadable' 状态之一时，您只需 continue 循环。但是 imin 和 imax 仍然有相同的值，所以你最终从向量中的相同位置读取相同的字符串，并发现它再次不可读，等等。您需要决定如何响应这些 'unreadable' 状态之一。我在上面猜到你想停止搜索，在这种情况下，要么设置标志并跳出循环，要么抛出异常来完成同样的事情。

Answer 2

创建指向您的数据项的指针列表。不要添加 "unreadable" 个。搜索结果指针列表。

Answer 3

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

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

 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() 函数 return 给定索引中第一个可比较元素的索引。方向不同。

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

二进制搜索避免不可读的条目（列表中的漏洞）

Binary Search avoid unreadable entry (hole in list)

c++

algorithm

binary-search