Блог

Главная - Вопросы по программированию - Создание двоичного поиска для использования в шаблонном списке std

Создание двоичного поиска для использования в шаблонном списке std

#c #list #templates #binary-search

#c #Список #шаблоны #двоичный поиск

Вопрос:

 template<typename C> bool binary_search(list<C>amp; a, C val) {
    typename list <C>::iterator it;
    typename list <C>::iterator it2;
    typename list <C>::iterator it3;

    size_t elements = a.size();

    for (it = a.begin(), it3 = a.end(); it != it3; ) {
        //find middle element
        elements = elements / 2;
        for (it2 = it; it2 < elements; it2  ) {
        }

        if (*it2 < val)
            *it = *it2;
        else if (*it2 > val)
            *it3 = *it2;
        else if (*it2 = val)
            return true;
        else
            return false;
    }
}

Привет! У меня возникли проблемы с реализацией этой функции поиска.
val в параметрах указано значение, которое мы ищем.

когда я пытаюсь скомпилировать код, я получаю

 error C2676: binary '<': 'std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>'
does not define this operator or a conversion to a type acceptable to the predefined operator

Эта ошибка возникает при:
for (it2 = it; it2 < elements; it2 )

также есть ли лучший способ найти средний элемент?

Комментарии:

1. Пожалуйста, добавьте комментарий к коду, который показывает, к какой строке относится ошибка.

2. Я предполагаю, что ошибка относится к it2 < elements : вы не можете сравнить итератор и целое число. В любом случае, вы не можете выполнять O(log(list size)) двоичный поиск по двусвязному списку.

3. @fas Это зависит от того, какие операции вы учитываете. Если вы учитываете только сравнения, но не улучшения итератора, возможна логарифмическая сложность.

4. Если вы также не учитываете сравнения, это может быть O (1)! Отличная идея!

Ответ №1:

elements содержит индекс последнего элемента, который вы хотите проверить. it2 является итератором. operator< не определено для этих типов. Вы можете использовать it и elements для создания итератора, чтобы сделать возможным сравнение.

 size_t elements = a.size();

    for (it = a.begin(), it3 = a.end(); it != it3; ) {
        //find middle element
        elements = elements / 2;
        auto end = std::next(it, elements); // added iterator

        for (it2 = it; it2 != end; it2  ) { // use added iterator
        }

        if (*it2 < val)
            *it = *it2;
        else if (*it2 > val)
            *it3 = *it2;
        else if (*it2 = val)   // note: this assigns val to *it2, probably a bug
            return true;
        else
            return false;
    }

Ответ №2:

Уверен, что это не очень хороший способ решить эту проблему, но это моя окончательная версия и работает для моего текущего задания.

 template<typename C> bool binary_search(list<C>amp; a, C val) {
    typename list <C>::iterator it;
    typename list <C>::iterator it2;
    typename list <C>::iterator it3 = a.end();

    size_t elements = a.size();
    size_t i = 0;

    for (it = a.begin(), it3--; it != it3; ) {
        //find middle element
        elements = elements / 2;
        for (it2 = it, i = 0; i < elements; it2  , i  ) {
        }

        if (*it2 < val)
            it = it2;
        else if (*it2 > val)
            it3 = it2;
        else if (*it2 = val)
            return true;
        else
            return false;
    }
}

Спасибо fas за указание на то, что было не так!

Ответ №3:

Чтобы переместить итератор на несколько мест, вы можете использовать std::advance :

 elements = elements / 2;
it2 = it;
std::advance(it2, elements);

Однако обратите внимание, что выполнение двоичного поиска в a std::list вряд ли будет эффективным, если у вас нет очень дорогостоящей функции сравнения. Если вам нужен произвольный доступ, вы должны использовать std::vector вместо этого. std::vector итераторы также позволяют вам просто добавлять к ним числа, не используя std::advance :

 elements = elements / 2;
it2 = it   elements;

Я предполагаю, что вы реализуете двоичный поиск в качестве упражнения, но если нет, обратите внимание, что в стандартной библиотеке есть функция двоичного поиска, у нее просто неочевидное имя: std::upper_bound std::lower_bound