10.7 Упражнения¶
10.7.1 Вопросы для самопроверки¶
1. Как двоичный поиск сужает область поиска¶
Найдите число 16 в упорядоченном массиве [2, 5, 8, 12, 16, 23, 38].
Используйте двойной замкнутый интервал [i, j] и середину
\(m=i+(j-i)/2\) с округлением вниз.
Для каждой итерации запишите (i, j, m), средний элемент и способ дальнейшего сужения интервала,
пока цель не будет найдена.
Ответ
Процесс поиска по итерациям:
| Итерация | (i, j, m) |
Средний элемент | Следующий шаг |
|---|---|---|---|
| 1 | (0, 6, 3) |
12 | 12 < 16, присвоить i = 4 |
| 2 | (4, 6, 5) |
23 | 23 > 16, присвоить j = 4 |
| 3 | (4, 4, 4) |
16 | Цель найдена, вернуть индекс 4 |
Массив упорядочен, поэтому если значение в середине меньше цели, можно исключить средний элемент и все элементы слева от него; если оно больше цели — исключить средний элемент и все элементы справа.
2. Левая и правая границы повторяющегося элемента¶
В массиве [1, 2, 2, 2, 4, 6] ищут число 2.
Ученик выполнил двоичный поиск, нашел цель по индексу 2, сразу вернул ответ и сказал:
«Индекс 2 — левая граница числа 2».
- Верно ли утверждение ученика? Чему равны левая и правая границы числа 2? Объясните ответ.
- В какой части массива нужно продолжить поиск левой границы, если средний элемент равен цели?
- В какой части нужно продолжить поиск правой границы? Достаточно указать направление, полный процесс поиска записывать не нужно.
Ответ
-
Утверждение неверно. Немедленный возврат после обнаружения числа 2 гарантирует лишь, что найден один из таких элементов, но не самый левый или самый правый. Левая граница в этом массиве имеет индекс 1, а правая — индекс 3.
-
При поиске левой границы, даже если средний элемент равен 2, нужно продолжить поиск слева, например, при двойном замкнутом интервале присвоить
j = m - 1. -
При поиске правой границы после совпадения среднего элемента с 2 нужно продолжить поиск справа, например, присвоить
i = m + 1.
3. Как выбрать способ поиска для разных данных¶
Для каждой ситуации выберите подходящий вариант из «линейный поиск, двоичный поиск, хеш-таблица» и объясните свой выбор.
- Многократно выполнять поиск среди \(10^7\) уже упорядоченных и больше не изменяющихся целых чисел, не создавая дополнительных структур данных;
- многократно проверять наличие ключа в наборе с частыми вставками и удалениями, не поддерживая порядок и не выполняя поиск по диапазону;
- один раз найти некоторое значение в неупорядоченном массиве.
Ответ
- Двоичный поиск: данные упорядочены и не меняются, сложность равна \(O(\log n)\), дополнительная память не нужна.
- Хеш-таблица: если хеш-функция достаточно равномерно распределяет ключи по бакетам, средняя временная сложность вставки, удаления и поиска по ключу равна \(O(1)\).
-
Прямой обход от начала до конца: ради одного поиска сортировка или построение хеш-таблицы все равно потребует предварительно обработать весь массив и не уменьшит общий объем работы для этой единственной задачи.
Выбор зависит от того, упорядочены ли данные, разрешено ли создавать дополнительную структуру, сколько будет запросов и какие операции нужно выполнять.
10.7.2 Задачи по программированию¶
1. Двоичный поиск в упорядоченном массиве¶
Дан массив целых чисел nums, упорядоченный строго по возрастанию, и целевое значение target. Найдите target с помощью двоичного поиска: если значение присутствует, верните его индекс в массиве; иначе верните -1.
Подсказки
- Начальный интервал задается как left = 0, right = n - 1; он непуст, пока left <= right
- Вычисляйте середину как mid = left + (right - left) // 2
- Если
nums[mid]меньшеtarget, перенесите левую границу вmid + 1; еслиnums[mid]большеtarget, перенесите правую границу вmid - 1; при равенстве сразу верните ответ
2. Позиция вставки в упорядоченный массив¶
Дан массив целых чисел nums, упорядоченный строго по возрастанию, и целевое значение target.
Если target уже находится в массиве, верните его индекс. Иначе верните позицию, в которую нужно вставить target, чтобы массив остался строго возрастающим. Ответ может быть равен 0 или длине массива. Используйте двоичный поиск.
Подсказки
- Ответ может быть равен 0 или длине массива n
- При двойном замкнутом интервале, если
nums[mid]больше или равноtarget, присвойтеright = mid - 1и продолжите проверять позиции левее; иначе присвойтеleft = mid + 1 - После завершения цикла left будет позицией вставки