Перейти к содержимому
Topos Uranos
Русский

Поиск и сортировка

Краткое содержание

Поиск и сортировка являются двумя основными задачами над коллекциями, и между ними существует компромисс: сортировка стоит один раз, но удешевляет каждый последующий поиск. В уроке вручную пишутся линейный и двоичный поиск, который на упорядоченных данных отбрасывает половину на каждом шаге; двоичный поиск обосновывается своим инвариантом, доказывается, что он завершается, подсчитываются его итерации и разбираются три ошибки, которые его губят. Затем идут сортировка выбором и сортировка вставками, с их инвариантами и точным подсчётом сравнений; после этого те же задачи решаются средствами библиотеки диапазонов, и проводится расчёт, который решает, когда выгодно отсортировать данные перед поиском.

Цели обучения

  1. Реализовывать линейный и двоичный поиск и обосновывать двоичный поиск его инвариантом («если значение есть, оно находится между low и high») вместе с доказательством того, что он завершается.
  2. Реализовывать сортировку выбором и сортировку вставками, формулировать инвариант каждой из них и подсчитывать их сравнения в лучшем и в худшем случае.
  3. Использовать std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search и std::ranges::lower_bound вместо собственных версий, когда это уместно, соблюдая их предусловия.
  4. Решать, исходя из числа предполагаемых поисков, выгодно ли отсортировать данные перед поиском в них, и обосновывать решение подсчётом сравнений.

Линейный поиск

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

Программа на C++
#include <cstddef>#include <print>#include <vector>​// Предусловие: нет.// Постусловие: возвращает наименьший индекс i, для которого values[i] == target,// или values.size(), если target нет.std::size_t linearSearch(const std::vector<int>& values, int target){    // Инвариант: target нет среди values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: не найдено", target);        } else {            std::println("{}: позиция {}", target, pos);        }    }}
Вывод
207: позиция 3112: позиция 1999: не найдено

Корректность обеспечивает инвариант строки 10. В начале, когда i равно 0, он утверждает нечто о пустой части и истинен. Если он верен в начале итерации и values[i] не является искомым, он верен и в её конце, уже с одним элементом больше. Однако у цикла два выхода: если выполняется return i;, то values[i] есть искомое значение и, по инварианту, ни один элемент до него искомым не был, откуда i есть первое вхождение (поэтому 112, которое встречается дважды, сообщается в позиции 1); если цикл заканчивается по условию, то i равно values.size(), и инвариант говорит, что значения нет нигде. Оператор return внутри цикла завершает функцию, а вместе с ней и цикл, и избавляет от флага.

Сложность в смысле урока Сложность алгоритма измеряется сравнениями values[i] == target. Если значения нет, их выполняется ровно nn, по одному на элемент: это худший случай. Если оно находится в позиции pp, их выполняется p+1p + 1. Линейный поиск, таким образом, имеет сложность O(n)O(n): вдвое больше данных, вдвое больше работы. Без дополнительных сведений лучше сделать нельзя: алгоритм, который не посмотрел бы на какой-то элемент, не знал бы, не там ли было значение.