c++ - 使用二分搜索从数组中删除字符串

Question

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

这是我的查找函数

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;

一旦您将数组 segmentation 到开始等于结束的点，就没有更多的空间可以搜索，并且您的字符串也不会被找到。

除此之外，我认为唯一可能有误的是您调用 Find 方法时使用了错误的范围。应该这样称呼:

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