Алгоритм двоичного поиска

Упорядоченная двоичная таблица

Основной недостаток

Преимущества

Удаление

Добавление

- Выполняется поиск. Если элемент найден, то завершение с ошибкой.

- Добавление записи выполняется как запись ключа и информации в запись, следующую за данными таблицы.

Перед записью необходимо проверить условие полноты таблицы С=S.

С + 2 =Тд = T’п + 2 – трудоемкость поиска

- Выполнить поиск записи с заданным ключом. Если запись не найдена, то завершение с ошибкой.

- Переписываем последнюю запись на место удаляемой и уменьшаем количество записей на 1.

С/2 + 3 = Ту = Тп +3 – трудоемкость удаления

1. Простые алгоритмы.
2. Таблица может быть реализована на основе массива или динамического списка.

Трудоемкость операции поиска, просмотр ½ или всех элементов.

Таблица называется упорядоченной двоичной, т.к. она упорядочена для двоичного поиска – отсортирована по ключам.

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

Поиск производиться делением пополам, пока не будет найден ключ или диапазон не станет пустым.

С – количество записей;

l, r - левая и правая границы поиска;

i, x – номер и значение ключа средней записи;

key – искомый ключ.

1. Устанавливается зона поиска: l=0, r=c-1.
2. Проверяется условие завершения поиска: r<l → ключ отсутствует, переход к п.6.
3. Вычисление номера средней записи: i=(l+r)/2.
4. Анализ ключа. Если key=x, то запись найдена, переход к п.6.

- если key<x – переход к верхней зоне, r=i-1;

- если key>x – переход к нижней зоне, l=i+1.

1. Переход к п.2.
2. Конец.

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

Тп = ]log₂C] – трудоемкость двоичного поиска

Дата добавления: 2014-01-15