Л7. Пошук у послідовності та обсяг роботи

Коротко про лекцію

Навчимося знаходити значення у послідовності та рахувати виконану роботу. Далі порівняємо алгоритми за зростанням цієї роботи разом із розміром даних.

У Л5 ми навчилися проходити елементи std::vector. У Л6 винесли окремі дії у функції та почали перевіряти їх через конкретні тести. Тепер застосуємо ці навички до однієї з базових задач програмування — пошуку.

Практичний сенс. Два алгоритми можуть давати однаково правильну відповідь, але виконувати дуже різний обсяг роботи на великих даних.

1. Спочатку формулюємо задачу пошуку

Нехай маємо послідовність:

4, 9, 13, 6

Потрібно відповісти на запитання: чи є в ній число 13?

Для такої задачі достатньо результату true або false. Функція може мати контракт:

contains(values, target)
вхід: послідовність values і шукане значення target
результат: true, якщо target є у values; інакше false

Задачу можна розв’язати простим правилом: перевіряти елементи по черзі, доки не знайдемо потрібний.

flowchart TD
    A["Взяти черговий елемент"] --> C{"value == target?"}
    C -- "так" --> D["Повернути true"]
    C -- "ні" --> E{"Є ще елементи?"}
    E -- "так" --> A
    E -- "ні" --> F["Повернути false"]

2. Лінійний пошук перевіряє елементи по черзі

Алгоритм, який переглядає елементи один за одним, називають лінійним пошуком. Слово «лінійний» тут пов’язане з тим, що кількість перевірок може зростати разом із кількістю елементів.

Перший варіант лише відповідає, чи знайдено значення.

#include <iostream>
#include <vector>

bool contains(const std::vector<int>& values, int target) {
    for (int value : values) {
        if (value == target) {
            // Перший збіг уже визначає відповідь, тому подальший перегляд не потрібний.
            return true;
        }
    }
    return false;
}

int main() {
    const std::vector<int> values{4, 9, 13, 6};

    // Два виклики показують обидва можливі результати: значення є або його немає.

    std::cout << "13: ";
    if (contains(values, 13)) {
        std::cout << "так\n";
    } else {
        std::cout << "ні\n";
    }

    std::cout << "8: ";
    if (contains(values, 8)) {
        std::cout << "так\n";
    } else {
        std::cout << "ні\n";
    }
}

Функція завершується одразу після першого збігу. Якщо цикл дійшов до кінця, функція повертає false.

2.1. Порядок елементів визначає кількість перевірок

Для target = 4 достатньо однієї перевірки. Для target = 6 потрібні чотири перевірки. Для відсутнього target = 8 теж доведеться переглянути всі чотири елементи.

Пошук	Перевірені значення	Кількість порівнянь
`4`	`4`	1
`13`	`4, 9, 13`	3
`6`	`4, 9, 13, 6`	4
`8`	`4, 9, 13, 6`	4

Тому корисно розрізняти звичайний і найважчий для алгоритму випадок.

Найгірший випадок — допустимий вхід із найбільшим обсягом роботи. Порівнюємо випадки для однакового розміру даних.

Для лінійного пошуку найгірший випадок виникає, коли потрібний елемент останній або відсутній.

Термін: найгірший випадок

Найгірший випадок — вхід, який змушує алгоритм виконати найбільший обсяг основної роботи серед входів однакового розміру.

3. Іноді треба повернути позицію

Питання «чи є значення?» дає логічний результат. Інша задача просить знайти його індекс.

Тоді контракт змінюється:

find_index(values, target)
результат: індекс першого збігу
якщо збігу немає: -1

Значення -1 тут має спеціальний домовлений зміст: «позицію не знайдено». Таке спеціальне значення називають сигнальним значенням.

Індекс std::vector має тип std::size_t. Наша функція повертає int, бо використовує від’ємне сигнальне значення. Тому знайдений індекс явно перетворюємо через уже знайомий static_cast<int>(...).

#include <iostream>
#include <vector>

int find_index(const std::vector<int>& values, int target) {
    for (std::size_t i{0}; i < values.size(); ++i) {
        if (values.at(i) == target) {
            return static_cast<int>(i);
        }
    }
    // -1 є домовленим сигналом: позицію target у послідовності не знайдено.
    return -1;
}

int main() {
    const std::vector<int> values{4, 9, 13, 6};

    std::cout << find_index(values, 13) << "\n";
    std::cout << find_index(values, 8) << "\n";
}

Для 13 функція повертає 2. Для 8 вона повертає -1.

3.1. Сигнальне значення входить до контракту

Число -1 саме по собі не пояснює значення. Його зміст визначає контракт функції. Код, який викликає find_index, повинен перевіряти цей результат до використання як позиції.

const int index{find_index(values, target)};

if (index == -1) {
    std::cout << "Значення відсутнє\n";
}

Спроба перетворити -1 на позицію std::vector створить окрему проблему. Тому результат пошуку спочатку інтерпретуємо, а потім використовуємо.

4. Порівнюємо алгоритми через кількість основних операцій

Час роботи програми залежить від комп’ютера, браузера, компілятора та інших процесів. Для першого аналізу зручніше рахувати основну дію алгоритму.

Для пошуку такою дією є порівняння:

value == target

Наступна функція повертає кількість виконаних порівнянь.

#include <iostream>
#include <vector>

int comparisons_until_found(const std::vector<int>& values, int target) {
    // Лічимо перевірки елементів, щоб оцінювати обсяг роботи незалежно від швидкості комп’ютера.
    int comparisons{0};

    for (int value : values) {
        ++comparisons;
        if (value == target) {
            return comparisons;
        }
    }

    return comparisons;
}

int main() {
    const std::vector<int> values{2, 5, 8, 11, 14, 17, 20, 23};
    std::cout << comparisons_until_found(values, 99) << "\n";
}

Для восьми елементів і відсутньої цілі результат дорівнює 8.

4.1. Позначаємо розмір входу через `n`

Для послідовності позначимо кількість елементів літерою n. Це дає змогу описувати алгоритм для різних розмірів одним правилом.

Термін: n

У цій лекції n означає кількість елементів у вхідній послідовності.

У розмові про ефективність часто використовують літеру n. Вона позначає розмір входу.

Для пошуку у std::vector природно взяти:

n = кількість елементів

Якщо n = 8, лінійний пошук у найгіршому випадку робить 8 порівнянь. Якщо n = 1000, може знадобитися 1000 порівнянь.

4.2. Що означає запис `O(n)`

Тепер введемо нове позначення.

O-нотація описує, як зростає обсяг роботи алгоритму зі збільшенням розміру входу. Запис O(n) читаємо як «порядку n».

Для лінійного пошуку найгірший випадок має O(n), бо подвоєння кількості елементів може приблизно подвоїти кількість перевірок.

O-нотація не задає точний час у мілісекундах. Воно описує характер зростання роботи.

Термін: O-нотація

O-нотація описує порядок зростання роботи зі збільшенням входу. Запис не передбачає точний час виконання конкретного комп’ютера.

flowchart TD
    N1["n = 10 → до 10 порівнянь"] --> N2["n = 100 → до 100 порівнянь"]
    N2 --> N3["n = 1000 → до 1000 порівнянь"]

5. Впорядкованість дає сильнішу інформацію

Розглянемо іншу послідовність:

2, 4, 7, 9, 13, 18, 21, 30, 42

Вона впорядкована за зростанням. Якщо середній елемент дорівнює 13, а ми шукаємо 30, усі значення ліворуч від 13 можна відкинути одразу.

Ця властивість дозволяє щоразу скорочувати область пошуку приблизно вдвічі.

Перед використанням такого алгоритму потрібна передумова:

Передумова двійкового пошуку

Послідовність має бути впорядкована за тим самим правилом, яке використовує порівняння в алгоритмі. Без цієї властивості відкидання половини діапазону необґрунтоване.

послідовність має бути впорядкована за тим самим правилом, яке використовує пошук.

Термін «передумова» ми вже використовували для функцій: це вимога, яка повинна виконуватися до початку алгоритму.

6. Двійковий пошук працює з інтервалом можливих позицій

Алгоритм, який щоразу перевіряє середину впорядкованого діапазону та відкидає половину позицій, називають двійковим пошуком.

Спочатку зберігаємо дві межі:

left  = перший можливий індекс
right = останній можливий індекс

Поточна середина:

const int middle{left + (right - left) / 2};

Далі маємо три випадки:

values[middle] == target — значення знайдено.
values[middle] < target — шукаємо правіше.
values[middle] > target — шукаємо лівіше.

flowchart TD
    A["діапазон left..right"] --> B["обчислити middle"]
    B --> C{"values[middle] == target?"}
    C -- "так" --> D["знайдено"]
    C -- "ні" --> E{"values[middle] < target?"}
    E -- "так" --> F["left = middle + 1"]
    E -- "ні" --> G["right = middle - 1"]
    F --> H{"left <= right?"}
    G --> H
    H -- "так" --> B
    H -- "ні" --> I["значення відсутнє"]

6.1. Повна реалізація

У коді межі зберігаємо як int. Розмір std::vector має тип std::size_t, тому перед обчисленням правої межі виконуємо явне перетворення.

#include <iostream>
#include <vector>

bool binary_contains(const std::vector<int>& values, int target) {
    // Якщо target існує, його можлива позиція весь час лишається між left і right.
    int left{0};
    int right{static_cast<int>(values.size()) - 1};

    while (left <= right) {
        const int middle{left + (right - left) / 2};
        const int value{values.at(static_cast<std::size_t>(middle))};

        if (value == target) {
            return true;
        }
        // Порівняння з середнім елементом дозволяє відкинути половину поточного інтервалу.
        if (value < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return false;
}

int main() {
    const std::vector<int> values{2, 4, 7, 9, 13, 18, 21, 30, 42};

    if (binary_contains(values, 21)) {
        std::cout << "знайдено\n";
    } else {
        std::cout << "немає\n";
    }

    if (binary_contains(values, 8)) {
        std::cout << "знайдено\n";
    } else {
        std::cout << "немає\n";
    }
}

Для порожнього std::vector вираз static_cast<int>(values.size()) - 1 дає -1. Тоді початкова умова left <= right одразу хибна, і цикл не виконується.

6.2. Простежимо один пошук вручну

Шукаємо 21 у дев’яти елементах.

Крок	`left`	`right`	`middle`	Значення	Рішення
1	0	8	4	13	шукати праворуч
2	5	8	6	21	знайдено

За два порівняння ми відкинули більшу частину послідовності.

7. Чому двійковий пошук росте повільніше

Кожний невдалий крок залишає приблизно половину попереднього діапазону.

flowchart TD
    A["32 позиції"] --> B["16"] --> C["8"] --> D["4"] --> E["2"] --> F["1"]

Для такого характеру зменшення використовують запис O(log n).

Тут log n можна читати практично: скільки разів можна ділити кількість можливих позицій приблизно навпіл, доки не залишиться одна.

`n`	Лінійний пошук, найгірший випадок	Двійковий пошук, приблизна верхня межа
8	8	4
16	16	5
32	32	6
1024	1024	близько 11

#include <iostream>
#include <vector>

int binary_comparisons(const std::vector<int>& values, int target) {
    // Межі задають частину впорядкованої послідовності, де target ще може перебувати.
    int left{0};
    int right{static_cast<int>(values.size()) - 1};
    int comparisons{0};

    while (left <= right) {
        const int middle{left + (right - left) / 2};
        // Одне збільшення відповідає одному порівнянню з середнім елементом.
        ++comparisons;
        const int value{values.at(static_cast<std::size_t>(middle))};

        if (value == target) {
            return comparisons;
        }
        if (value < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return comparisons;
}

int main() {
    const std::vector<int> values{
        1, 3, 5, 7, 9, 11, 13, 15,
        17, 19, 21, 23, 25, 27, 29, 31
    };

    std::cout << binary_comparisons(values, 31) << "\n";
}

Для шістнадцяти впорядкованих значень пошук останнього елемента виконує п’ять порівнянь у цій реалізації.

8. Передумова двійкового пошуку є частиною правильності

Алгоритм вирішує, яку половину відкинути, виходячи з порядку значень. Для невпорядкованої послідовності це рішення втрачає підставу.

#include <iostream>
#include <vector>

// Функція покладається на зростаючий порядок values і сама цю передумову не перевіряє.
bool binary_contains(const std::vector<int>& values, int target) {
    int left{0};
    int right{static_cast<int>(values.size()) - 1};

    while (left <= right) {
        const int middle{left + (right - left) / 2};
        const int value{values.at(static_cast<std::size_t>(middle))};

        if (value == target) {
            return true;
        }
        if (value < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return false;
}

int main() {
    // Тут навмисно порушено передумову: двійковий пошук очікує впорядковані дані.
    const std::vector<int> values{10, 1, 7, 3, 9};

    if (binary_contains(values, 1)) {
        std::cout << "знайдено\n";
    } else {
        std::cout << "не знайдено\n";
    }
}

Число 1 реально присутнє у std::vector, але алгоритм повідомляє протилежне. Помилка виникла через порушену передумову.

Тому правильність алгоритму складається з двох частин:

реалізація відповідає алгоритму;
вхідні дані відповідають його передумовам.

9. Вибір пошуку залежить від даних і задачі

Лінійний пошук має сильну перевагу: він працює для будь-якого порядку елементів.

Двійковий пошук використовує впорядкованість і виконує значно менше порівнянь на великих даних. Але впорядкованість треба мати або створити заздалегідь.

Якщо маємо невелику послідовність і один пошук, простий лінійний алгоритм часто достатній. Для великої впорядкованої послідовності та багатьох пошуків двійковий алгоритм стає особливо корисним.

O-нотація допомагає порівняти зростання роботи. Воно не замінює перевірку передумов і правильності.

Як обґрунтовувати вибір алгоритму

Назвіть властивості вхідних даних, очікуваний обсяг роботи та важливі передумови. Потім поясніть обмеження вибраного алгоритму для цієї задачі.

10. Тести для алгоритму пошуку

Для пошуку потрібні випадки, що перевіряють різні позиції та відсутність цілі:

порожня послідовність;
один елемент, який збігається;
один елемент, який не збігається;
перший елемент;
середній елемент;
останній елемент;
відсутнє значення.

Для двійкового пошуку додається ще одна перевірка: вхід має бути впорядкованим.

#include <cassert>
#include <iostream>
#include <vector>

// Тести передають лише впорядковані дані, бо це передумова двійкового пошуку.
bool binary_contains(const std::vector<int>& values, int target) {
    int left{0};
    int right{static_cast<int>(values.size()) - 1};

    while (left <= right) {
        const int middle{left + (right - left) / 2};
        const int value{values.at(static_cast<std::size_t>(middle))};

        if (value == target) {
            return true;
        }
        if (value < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return false;
}

int main() {
    const std::vector<int> empty{};
    const std::vector<int> one{5};
    const std::vector<int> ordered{1, 3, 5, 7, 9};

    // Набір перевіряє порожній ввід, один елемент, межі та відсутнє значення.
    assert(!binary_contains(empty, 5));
    assert(binary_contains(one, 5));
    assert(binary_contains(ordered, 1));
    assert(binary_contains(ordered, 9));
    assert(!binary_contains(ordered, 4));

    std::cout << "Тести пройдено\n";
}

Набір тестів перевіряє порожній вхід, одну позицію, обидві межі та відсутнє значення.

11. Робочий порядок для задачі пошуку

Визначте, який результат потрібен: наявність, індекс або саме значення.
Запишіть контракт функції для випадку «знайдено» і «не знайдено».
Перевірте, чи має послідовність корисну передумову, наприклад впорядкованість.
Виберіть алгоритм, який відповідає цій передумові.
Назвіть основну операцію та оцініть її кількість.
Перевірте межові позиції та відсутню ціль.
Для оптимізованого алгоритму окремо перевірте передумову.

12. Інтерактивна самоперевірка лекції

Самоперевірка вимагає трасувати пошук, рахувати порівняння, знаходити порушені передумови та порівнювати характер зростання роботи.