c++ - 如何使用Binary Search返回姓氏(给定字符串)的第一个索引/出现?

标签 c++ c++11 struct binary-search find-occurrences

我正在为我的类(class)分配作业,此函数的目标是在结构数组上使用Binary Sort,并返回找到姓氏的第一个位置的索引(即使有多个姓氏也是如此) ,只需返回第一个)。我的代码几乎可以完美地完成我的工作,但是当我打印索引时,我得到的输出太多了。例如,如果我这样调用我的函数,并且将字符串“Zulauf”作为姓氏:

cout << binaryFindFirstByLastName("Zulauf", person, total) << endl;

我得到的是99811,而不是它的实际位置99812(显然是从大文件中读取)。任何帮助或一般建议将不胜感激,谢谢!
int binaryFindFirstByLastName(const std::string& value, const Person* array, int size) {
int low = 0;
int high = size-1;
int mid = (low + high) / 2;
while (low + 1 != high) {
    mid = (low + high) / 2;
    if (array[mid].last < value) {
        low = mid;
    }
    else {
        high = mid;
    }
    mid = (low + high) / 2;
}
if (high > size || array[high].last != value) {
    return -1;
}
else return high;
}

最佳答案

让我们逐步介绍一下算法。为了简单起见,我将在这里使用整数。

首先,我们有循环条件。我们应该使用low < high,因为我们希望将搜索范围缩小到一个元素,以便稍后我们可以检查它是否是循环之外的目标,或者在low最终成为high + 1的情况下(搜索未命中)。

现在,让我们看一下循环主体中可能发生的三种情况。如果我们的目标值大于当前元素,我们需要low = mid + 1,因为目标的最左位置可能是右边的下一个元素。如果目标值小于当前元素,则相同。如果目标值等于当前元素,则我们需要hi = mid,因为该元素可能是我们正在寻找的元素,或者可能在左侧。

循环退出后,我们需要处理两种情况。如果是low > high,显然我们会错过搜索。否则,我们需要检查剩余的元素以查看其是否等于我们的目标。

全部放在一起:

int binarySearch(const int &value, const int *a, const int &size)
{
    int low = 0, high = size - 1;
    //Note that these do have to be signed types, since high could be -1
    while(low < high)
    {
        int mid = low + (high - low) / 2;
        //a way to find the average without any chance of overflow
        if(value == a[mid])
        {
            high = mid;
        }
        else if(value < a[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return (low > high || a[low] != value) ? -1 : low;
}

还有其他方法可以实现,但我发现这种方法是最简单的。

关于c++ - 如何使用Binary Search返回姓氏(给定字符串)的第一个索引/出现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49724959/

相关文章:

这个 memcpy 会导致未定义的行为吗?

c++ - 字段 'tile' 无法使用 typedef 结构解析

c++ - 具有默认值的结构的大括号(聚合)初始化

c++ - 来自二维数组的特征图

c++ - 什么构造函数被调用,它不是移动

c - 如何传递结构数组中的名称值作为C中的引用?

c - struct函数中的“*”是什么?

c++ - 为什么可以分配具有 const 成员的结构?

c++ - 如何记录一个需要回调的函数?

c++ - 宏守卫在标题中不起作用