Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 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».

1. Верно ли утверждение ученика? Чему равны левая и правая границы числа 2? Объясните ответ.
2. В какой части массива нужно продолжить поиск левой границы, если средний элемент равен цели?
3. В какой части нужно продолжить поиск правой границы? Достаточно указать направление, полный процесс поиска записывать не нужно.

Ответ

1. Утверждение неверно. Немедленный возврат после обнаружения числа 2 гарантирует лишь, что найден один из таких элементов, но не самый левый или самый правый. Левая граница в этом массиве имеет индекс 1, а правая — индекс 3.

2. При поиске левой границы, даже если средний элемент равен 2, нужно продолжить поиск слева, например, при двойном замкнутом интервале присвоить `j = m - 1`.

3. При поиске правой границы после совпадения среднего элемента с 2 нужно продолжить поиск справа, например, присвоить `i = m + 1`.

### 3. Как выбрать способ поиска для разных данных

Для каждой ситуации выберите подходящий вариант из «линейный поиск, двоичный поиск, хеш-таблица» и объясните свой выбор.

1. Многократно выполнять поиск среди \(10^7\) уже упорядоченных и больше не изменяющихся целых чисел, не создавая дополнительных структур данных;
2. многократно проверять наличие ключа в наборе с частыми вставками и удалениями, не поддерживая порядок и не выполняя поиск по диапазону;
3. один раз найти некоторое значение в неупорядоченном массиве.

Ответ

1. Двоичный поиск: данные упорядочены и не меняются, сложность равна \(O(\log n)\), дополнительная память не нужна.
2. Хеш-таблица: если хеш-функция достаточно равномерно распределяет ключи по бакетам, средняя временная сложность вставки, удаления и поиска по ключу равна \(O(1)\).

3. Прямой обход от начала до конца: ради одного поиска сортировка или построение хеш-таблицы все равно потребует предварительно обработать весь массив и не уменьшит общий объем работы для этой единственной задачи.

   Выбор зависит от того, упорядочены ли данные, разрешено ли создавать дополнительную структуру, сколько будет запросов и какие операции нужно выполнять.

## 10.7.2 Задачи по программированию

### 1. Двоичный поиск в упорядоченном массиве

Дан массив целых чисел `nums`, упорядоченный строго по возрастанию, и целевое значение `target`. Найдите `target` с помощью двоичного поиска: если значение присутствует, верните его индекс в массиве; иначе верните -1.

Подсказки

1. Начальный интервал задается как left = 0, right = n - 1; он непуст, пока left <= right
2. Вычисляйте середину как mid = left + (right - left) // 2
3. Если `nums[mid]` меньше `target`, перенесите левую границу в `mid + 1`; если `nums[mid]` больше `target`, перенесите правую границу в `mid - 1`; при равенстве сразу верните ответ

LeetCode

### 2. Позиция вставки в упорядоченный массив

Дан массив целых чисел `nums`, упорядоченный строго по возрастанию, и целевое значение `target`.

Если `target` уже находится в массиве, верните его индекс. Иначе верните позицию, в которую нужно вставить `target`, чтобы массив остался строго возрастающим. Ответ может быть равен 0 или длине массива. Используйте двоичный поиск.

Подсказки

1. Ответ может быть равен 0 или длине массива n
2. При двойном замкнутом интервале, если `nums[mid]` больше или равно `target`, присвойте `right = mid - 1` и продолжите проверять позиции левее; иначе присвойте `left = mid + 1`
3. После завершения цикла left будет позицией вставки

LeetCode

##### Оставляйте свои идеи, вопросы и предложения в комментариях