2. Двоичный поиск, оценка эффективности и её обоснование. Программа bin_search и её особенности.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Практические приложения метода двоичного поиска разнообразны:
Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до
можно за время
.
Когда аргумент дискретен, и изначально
лежит на отрезке длины N,
поиск решения займёт
времени.
Наконец, для поиска экстремума, скажем
для определённости минимума,
на очередном шаге отбрасывается тот
из концов рассматриваемого отрезка,
значение в котором максимально.
3.Бинарное дерево поиска, особенности его построения. Примеры.
Дерево — это иерархическая структура данных, состоящая из элементов
(вершин, или узлов), которые связаны между собой отношениями типа «роди-
тельская вершина – дочерняя вершина».
Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
Оба поддерева — левое и правое, являются двоичными деревьями поиска.
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако, это касается реализации, а не природы двоичного дерева поиска.
Для целей реализации двоичное дерево поиска можно определить так:
Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент.
Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.
Базовый интерфейс двоичного дерева поиска состоит из трех операций:
FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.
Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:
«Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека, и операцией добавления новой записи.
Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.
Namespace — хранилище имен переменных с их значениями, возникающее в трансляторах языков программирования.
Example:
Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево. Первым узлом в дереве (корнем) станет узел со значением 20. Обратить внимание: поиск места подключения очередного элемента всегда начинается с корня. К корню слева подключается элемент 10. К корню справа подключается элемент 35. Далее элемент 15 подключается справа к 10, проходя путь: корень 20 - налево - элемент 10 - направо - подключение, так как дальше пути нет. Процесс продолжается до исчерпания включаемых элементов. Результат представлен на рис. 10.
