В разных источниках по-разному описана работа функций qLowerBound() и qUpperBound(), используемых для нахождения элемента с помощью алгоритма бинарного дерева. Здесь приведены примеры, демонстрирующие что делают данные функции.

Первое, что нужно знать: данные алгоритмы работают только с отсортированными последовательностями. Если последовательность будет неотсортирована, результат будет неопределен. В последовательности допустимы повторяющиеся элементы.

Второе что нужно знать, это то, что данные алгоритмы выполняют поиск с помощью бинарного дерева. То есть, вычислительная сложность нахождения элемента O(log n), что гораздо лучше линейного поиска O(n).

И самое главное, что нужно понимать. qLowerBound() и qUpperBound() - это не функции-антагонисты, одна из которых находит элемент со значением меньше заданного, а вторая - больше чем задано. Точное назначение этих функций написано в следующих определениях:

qLowerBound() - Нахождение элемента со значением, больше либо равно заданному

qUpperBound() - Нахождение элемента со значением, больше заданному

Вот так, наименование qLowerBound() не говорит о том, что будет произведен поиск со значением меньше заданного. Если этой особенности не знать, на этом можно споткнуться.

Функции qLowerBound() и qUpperBound() сделаны, в частности, для того, чтобы находить границы повторяющихся значений в контейнерах.

Чтобы понимать, что могут возвращать эти функции, можно рассмотреть следующий код (функция lessThan() даже не нужна, потому что для типа целых положительных и так существует оператор <, но когда будет разрабатываться сравнение других типов, можно по-быстрому сделать такую функцию по приведенному образу и подобию):

bool lessThan(const unsigned int &a, const unsigned int &b)

{

return a < b;

}

...

QList<unsigned int> values;

values << 1 << 12 << 32 << 51 << 64 << 81 << 88 << 91 << 98;

qDebug() << values;

unsigned int valueForFindPos=70;

qDebug() << "Value for find pos: "<< valueForFindPos;

QList<unsigned int>::const_iterator result = qLowerBound (values.begin(),

values.end(),

valueForFindPos,

lessThan);

if (result == values.constEnd())

qDebug() << "Found end of list";

else

qDebug() << "Found element: " << *result;

В этой программе происходит попытка поиска несуществующего значения 70. Вывод этой программы будет следующий:

(1, 12, 32, 51, 64, 81, 88, 91, 98)

Value for find pos: 70

Found element: 81

Если же заменить qLowerBound() на qUpperBound(), то вывод не изменится.

Результаты данных функций будут различны только в том случае, если будет точно найден сравниваемый элемент. Для qLowerBound() и значения 51 результат будет следующим:

(1, 12, 32, 51, 64, 81, 88, 91, 98)  

Value for find pos:  51  

Found element:  51

А для qUpperBound() и значения 51 результат будет следующим:

(1, 12, 32, 51, 64, 81, 88, 91, 98)  

Value for find pos:  51  

Found element:  64

Если же в данной последовательности будет несколько значений 51, то qLowerBound() вернет итератор на первую левую ячейку со значением 51, а функция qUpperBound() вернет итератор на ячейку, следующую за самой правой ячейкой со значением 51, то есть на ячейку со значением 64.