使用两段搜索从数组中删除字符串

Question

我有两个函数。函数Find执行两部分搜索，这意味着它按部分搜索数组，直到找到键并返回其位置。函数removef或(remove fast)获取该位置并将其从字符串数组中删除。我使用的是一个命令行界面，它要求用户输入一个命令和一个字符串(字符串正在被删除)，因此没有必要提示用户输入字符串。

下面是我的Find函数

int StringList::Find(string key, int start, int end)
{
    int middle = (end + start)/2;
    if (key > str[middle])
    {
        return Find(key,middle,end);
    }
    else if ( key < str[middle])
    {
        return Find(key,start,middle);
    }
    else if (key == str[middle])
    {
        return middle;
    }
}

Find函数应该确定键是在数组的上半部分还是下半部分(中上或中下)，然后继续划分，直到找到需要删除的键或字符串。

下面是removef：

void StringList::removef(string s)
{
    int loc = Find(s,0,10000); //ignore these parameters, i know they are wrong they are just an example


        for(int j=loc; j<(numberOfStrings)-1; j++)
        {
            str[j] = str[j+1];
        }
        numberOfStrings--;

}

我的问题是我的Find函数使用了两段式搜索。有什么我可以修复的建议吗？我真的卡住了。谢谢!

Answer 1

我能看到的一个问题是，当键大于中间元素时，您将新范围设置为[midde,end]，但它应该是[middle+1,end] -没有必要再次考虑中间元素，因为您已经知道它不匹配。

因此，第一个条件应该如下所示：

if (key > str[middle])
{
    return Find(key,middle+1,end);
}

此外，正如其他人所提到的，您需要检查字符串是否不在数组中。我建议在Find方法的开头添加类似下面这样的内容。

if (start == end) return -1;

一旦将数组细分到start等于end的程度，就没有更多的空间可供搜索，字符串wron也找不到了。

除此之外，我认为唯一可能是错误的是您使用错误的范围调用了Find方法。应该是这样命名的：

int loc = Find(s,0,numberOfStrings);

Answer 2

首先，我假设您已经对字符串'str‘进行了排序，array...otherwise二进制搜索将不起作用。

在你的'Find‘函数中，你可以访问'str’数组，我假设它就是你的字符串数组，但是你没有把这个数组作为参数传递。因此，除非它是一个试图访问它的全局数组，否则它将无法工作。

最后，由于要递归调用此函数，因此需要有一个case来处理根本不包含在数组中的字符串。