Алгоритмы поиска
| English | Русский |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Поиск |
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
| binary search/ˈbaɪnəri sɜːtʃ/ | бинарный поиск |
| sorted/ˈsɔːtɪd/ | отсортированы |
Поиск значения
- Поиск означает нахождение целевого значения в коллекции.
- Два стандартных алгоритма: линейный поиск и бинарный поиск.
- Оба возвращают индекс, где находится цель, или сигнал «не найдено» (часто
-1). - Какой из них можно использовать, зависит от того, отсортированы ли данные.
Линейный поиск
- Проверяйте каждый элемент начиная с начала, один за другим, пока не найдете цель.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Работает на любом массиве — отсортированном или нет.
- Худший случай: он смотрит на каждый элемент (
nпроверок).
Бинарный поиск
- Требует отсортированного массива. Каждый раз смотрите на средний элемент.
- Если средний элемент — цель, готово. Если цель меньше, ищите в левой половине; если больше, в правой половине.
- На каждом шаге диапазон поиска уменьшается вдвое.
- Гораздо быстрее на больших отсортированных массивах — около
log₂ nпроверок, а неn.
Почему бинарный поиск быстрый
- Линейный поиск миллиона элементов: до миллиона проверок.
- Бинарный поиск миллиона отсортированных элементов: около 20 проверок.
- Подвох: массив должен быть уже отсортирован.
- Повторное деление пополам — главная идея, лежащая в основе
O(log n).
Бинарный поиск работает только на ОТНОРИРОВАННОМ массиве — его запуск на неотсортированных данных даст неверные ответы. Он также сравнивает со средним элементом и отбрасывает половину диапазона на каждом шаге; линейный поиск сравнивает начиная с начала и убирает всего один элемент. Если вы не уверены, что данные отсортированы, нужно использовать линейный поиск (или сначала отсортировать).
Бинарный поиск числа 7 в [1, 3, 5, 7, 9]:
- Средний элемент —
5(индекс 2). 7 > 5, поэтому ищем правую половину. - Правая половина
[7, 9]; середина7. Найдено на индексе 3. - Две проверки вместо четырех — диапазон уменьшался вдвое каждый раз.
Линейный поиск проверяет элементы с начала (работает на любом массиве, до n проверок). Бинарный поиск требует отсортированного массива, сравнивает со средним элементом и уменьшает диапазон поиска вдвое на каждом шаге (около log₂ n проверок). Оба возвращают найденный индекс или сигнал «не найдено», такой как -1.
Линейный против бинарного поиска
Бинарный поиск на каждом шаге уменьшает отсортированный диапазон вдвое.
Линейный поиск...
Линейный = от начала до конца; работает с любым массивом.
Бинарный поиск требует, чтобы массив был...
Бинарный поиск работает только с отсортированными данными.
Каждый шаг бинарного поиска...
Он сравнивает с серединой и оставляет одну половину.
Бинарный поиск в [1,3,5,7,9] для 7: сколько сравнений (середина каждый раз)?
Сравнение с 5, затем с 7 — два сравнения.
Бинарный поиск дает правильные результаты в НЕОТСОРТИРОВАННОМ массиве.
Он опирается на порядок; неупорядоченные данные нарушают его работу.
Сопоставьте каждый алгоритм поиска с его свойством.
Линейный поиск универсален, но медленнее; бинарный быстрый, но требует порядка.