ответы сессия довгалюк 2 семестр. Определение Правосторонний бинарный поиск
 Скачать 3.01 Mb.
|
|
Принцип работы[править] Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие — это левосторонний/правосторонний двоичный поиск. Правосторонний/левосторонний целочисленный двоичный поиск[править] Для простоты дальнейших определений будем считать, что a[−1]=−∞a[−1]=−∞ и что a[n]=+∞a[n]=+∞ (массив нумеруется с 00).
Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций [l,r][l,r] таких, что ∀i∈[l,r]:a[i]=x∀i∈[l,r]:a[i]=x и ∀i∉[l,r]:a[i]≠x∀i∉[l,r]:a[i]≠x Пример:[править] Задан отсортированный массив [1,2,2,2,2,3,5,8,9,11],x=2[1,2,2,2,2,3,5,8,9,11],x=2. Правосторонний поиск двойки выдаст в результате 44, в то время как левосторонний выдаст 11 (нумерация с нуля). Отсюда следует, что количество подряд идущих двоек равно длине отрезка [1;4][1;4], то есть 44. Если искомого элемента в массиве нет, то правосторонний поиск выдаст максимальный элемент, меньший искомого, а левосторонний наоборот, минимальный элемент, больший искомого. Алгоритм двоичного поиска[править] Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. Если искомое больше(в случае правостороннего — не меньше), чем элемент сравнения, то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1 Несколько слов об эвристиках[править] Эвристика с завершением поиска, при досрочном нахождении искомого элемента Заметим, что если нам необходимо просто проверить наличие элемента в упорядоченном множестве, то можно использовать любой из правостороннего и левостороннего поиска. При этом будем на каждой итерации проверять "не попали ли мы в элемент, равный искомому", и в случае попадания заканчивать поиск. Эвристика с запоминанием ответа на предыдущий запрос Пусть дан отсортированный массив чисел, упорядоченных по неубыванию. Также пусть запросы приходят в таком порядке, что каждый следующий не меньше, чем предыдущий. Для ответа на запрос будем использовать левосторонний двоичный поиск. Алгоритм может быть определен в рекурсивной и нерекурсивной формах. Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии. Количество шагов поиска определится как log2n↑, Все эти задачи решаются бинарным поиском за O(logn). Динамическое программирование — метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи Решение задачи динамическим программированием должно содержать следующее: · Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло — придётся думать · Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно Чтобы успешно решить задачу динамикой нужно: 1) Состояние динамики: параметр(ы), однозначно задающие подзадачу. 2) Значения начальных состояний. 3) Переходы между состояниями: формула пересчёта. 4) Порядок пересчёта. 5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний. Порядок пересчёта |
