Recursive Searching and Sorting
Введено
13:31
Data Collections (Наборы данных)
Сделайте одно фото на телефоне. Для компьютера это вовсе не картинка — это сетка чисел, по одному на каждый пиксель, около двенадцати миллионов из них. Попробуйте теперь…
Озвучивание на английском · переключаемые субтитры на английском и китайском языках
In this lesson
| English | Значение |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | разделяй и властвуй |
| merge sort/mɜːdʒ sɔːt/ | сортировка слиянием |
| merge/mɜːdʒ/ | слияние |
Рекурсия в поиске и сортировке
- Та же идея разделяй и властвуй лежит в основе рекурсивного бинарного поиска и сортировки слиянием.
- Разделите задачу пополам, решите половины, объедините.
- Рекурсивный бинарный поиск ищет в одной половине, вызывая сам себя для неё.
- Сортировка слиянием сортирует каждую половину, затем сливает отсортированные половины вместе.

Рекурсивный бинарный поиск
- Базовый случай: пустой диапазон означает, что целевой элемент не найден.
- Посмотрите на средний элемент. Если это цель, верните его индекс.
- Если цель меньше, рекурсируйте по левой половине; если больше, то по правой.
- Каждый вызов делит диапазон пополам — та же сложность
O(log n), записанная рекурсивно.
Сортировка слиянием
- Разделите массив на две половины; отсортируйте каждую половину рекурсивно.
- Базовый случай: массив из 0 или 1 элемента уже отсортирован.
- Слияние: пройдите обе отсортированные половины, всегда беря меньший элемент спереди.
- Гораздо быстрее, чем
n²сортировки — околоn log nработы.
Почему побеждает «разделяй и властвуй»
- Деление задачи пополам на каждом шаге дает коэффициент
log n. - Сортировка слиянием
n log nпревосходит сортировку выбором/вставкойn²на больших массивах. - Базовый случай (пустой или один элемент) останавливает каждую ветвь.
- Та же форма, что и у любой рекурсии: разделение вниз, объединение вверх.
Рекурсивный бинарный поиск рекурсирует только по ОДНОЙ половине (цель находится только с одной стороны); сортировка слиянием рекурсирует по ОБЕИМ половинам, а затем сливает их. Обе требуют базового случая — пустой диапазон означает «не найдено» для поиска; массив из 0 или 1 элемента уже отсортирован для сортировки слиянием. Именно «разделяй и властвуй» делает их быстрыми (O(log n) и O(n log n)).
Сортировка слиянием на [3, 1, 2, 4]:
- Разделите на
[3, 1]и[2, 4]; отсортируйте каждую →[1, 3]и[2, 4]. - Слияние: возьмите 1, затем 2, затем 3, затем 4 →
[1, 2, 3, 4]. - При каждом слиянии по очереди выбирается меньший элемент из начала каждого списка.
Рекурсивный двоичный поиск рекурсирует по одной половине (базовый случай: пустой диапазон = не найдено) для O(log n) поиска. Сортировка слиянием рекурсирует по обеим половинам и сливает их (базовый случай: 0 или 1 элемент) для O(n log n) сортировки. Оба подхода используют метод «разделяй и властвуй»: разбивают задачу вниз и объединяют результаты вверх — это значительно быстрее, чем n².
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
The target is only on one side of the middle.
Merge sort recurses on...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
One (or zero) element needs no sorting.
Merge sort's running time is about...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Always take the smaller front element: 1, 2, 3, 4.