Как вернуть первый индекс / вхождение фамилии (заданной строки) с помощью бинарного поиска?
Я работаю над заданием для своего класса, и цель этой функции — использовать двоичную сортировку в массиве структуры и вернуть индекс самого первого местоположения, где найдена фамилия (даже если существует несколько фамилий Верни первый). Мой код работает почти идеально для того, что я пытаюсь сделать, но когда я печатаю индекс, я получаю вывод 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;
}
Решение
Давайте просто пройдемся по алгоритму шаг за шагом. Я собираюсь использовать здесь только для простоты.
Во-первых, у нас есть условие цикла. Мы должны использовать 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;
}
Есть и другие способы, которыми это может быть реализовано, но я считаю этот способ наиболее простым.
Другие решения
Для полноты, в реальном мире, мы использовали бы готовую библиотечную шаблонную функцию 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);
}));
}