<<
>>

Линейный и бинарный поиск

Алгоритмы qFind() и qBinaryFind() в качестве параметров получают итераторы диапазона и значение, а возвращают итератор на элемент, который соответствует данному значению, или "end" итератор, если не найдено ни одного элемента.

Алгоритм бинарного поиска намного быстрее чем линейный алгоритм, но он может работать только с сортированными диапазонами.

Если значение встречается более одного раза, qFind() вернет итератор на первый элемент, тогда как qBinaryFind() на произвольный.

Для большей гибкости, Qt 4 предоставляет qLowerBound() и qUpperBound(). Как и qBinaryFind(), они работают с сортированным диапазоном. Если значение найдено, qLowerBound() вернет итератор на первый найденный элемент, а qUpperBound() вернет итератор, указывающий на следующий за последним элемент. Если значение не найдено, они вернут итератор на позицию, в которую данный элемент может быть вставлен.

Частый пример использования qLowerBound() и qUpperBound() это проход по всем вхождениям значения:

QStringList list;

QStringList::iterator i, j;

...

i = qLowerBound(list.begin(), list.end(), value);

j = qUpperBound(list.begin(), list.end(), value);

while (i != j) {

processItem(*i);

++i;

}

<< | >>
Источник: Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms). 2000

Еще по теме Линейный и бинарный поиск:

  1. ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
  2. Поиск смысла жизни – это поиск бессмертия!
  3. Линейно-функциональные структуры.
  4. Линейный и нелинейный умы
  5. Линейные структуры.
  6. Линейный ум-эго
  7. Модификации линейной организационной структуры.
  8. Линейный и нелинейный ум
  9. Линейное и нелинейное мышление
  10. Линейное и нелинейное мышление
  11. Линейный и нелинейный умы
  12. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  13. ПОИСК ИНФОРМАЦИОННЫЙ
  14. ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»