c++ - 如何使用二进制搜索返回姓氏(给定字符串)的第一个索引/出现？

Question

我正在为我的类(class)做作业，这个函数的目标是对结构数组使用二进制排序，并返回找到姓氏的第一个位置的索引(即使有多个姓氏，只返回第一个)。我的代码几乎完美地完成了我想要做的事情，但是当我打印索引时，我得到的输出太多了 1。例如，如果我用字符串“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;
}

Answer 1

为了完整性，在现实世界中，我们将使用现成的库模板函数std::lower_bound:

c++11 版本:

#include <algorithm>

struct Person
{
    std::string last;
};

struct last_is_less
{
    bool operator()(std::string const& l, Person const& r) const
    {
        return l < r.last;
    }

    bool operator()(Person const& l, std::string const& r) const
    {
        return l.last < r;
    }
};

int binaryFindFirstByLastName(const std::string& value, const Person* array, int size) {
    auto first = array;
    auto last = array + size;
    auto i = std::lower_bound(first, last, value, last_is_less());
    if (i == last || i->last != value)
        return -1;
    return int(std::distance(first, i));
}

c++14版本，使用自由函数:

bool last_name_is_less(std::string const& l, Person const& r)
{
    return l < r.last;
}

bool last_name_is_less(Person const& l, std::string const& r)
{
    return l.last < r;
}

// using lambda to aid in expressing semantic intent
//
int binaryFindFirstByLastName2(const std::string& value, const Person* array, int size) {

    auto first = array;
    auto last = array + size;

    auto to_index = [&](auto iter) 
    {
        if (iter == last || iter->last != value)
            return -1;
        return int(std::distance(first, iter));
    };

    return to_index(std::lower_bound(first, last, 
                                     value, 
                                     [](auto&& l, auto&& r) 
                                     { 
                                         return last_name_is_less(l, r); 
                                     }));
}