Мультипликативный бинарный поиск - Multiplicative binary search
 | Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Сентябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
 Визуализация алгоритма мультипликативного двоичного поиска, где 7 - целевое значение. | |
| Учебный класс | Алгоритм поиска |
|---|---|
| Структура данных | Множество |
| Худший случай спектакль | О(бревно п) |
| Лучший случай спектакль | О(1) |
| Средний спектакль | О(бревно п) |
| Худший случай космическая сложность | О(1) |
В Информатика, мультипликативный двоичный поиск это вариант бинарный поиск который использует определенную перестановку ключей в массиве вместо сортированного порядка, используемого обычным двоичным поиском.[1]Мультипликативный двоичный поиск был впервые описан Томасом Стэндишем в 1980 году. Этот алгоритм был первоначально предложен для упрощения вычисления индекса средней точки на небольших компьютерах без эффективных операций деления или сдвига. тайник -дружественный характер мультипликативного двоичного поиска делает его подходящим для вне ядра Поиск по блочно-ориентированный хранение как альтернатива B-деревья и B + деревья. Для оптимальной производительности фактор ветвления B-дерева или B + -дерева должны соответствовать размеру блока файловая система что он хранится. Перестановка, используемая при мультипликативном двоичном поиске, помещает оптимальное количество ключей в первое (корень ) независимо от размера блока.
Мультипликативный бинарный поиск используется некоторыми оптимизация компиляторов реализовать операторы переключения.[2][3]
Алгоритм
Мультипликативный двоичный поиск работает с переставленным отсортированным массивом. Ключи хранятся в массиве в последовательности уровней соответствующих сбалансированных двоичное дерево поиска Это помещает первую точку бинарного поиска в качестве первого элемента в массиве. Вторые опорные точки размещаются на следующих двух позициях.
Учитывая массив А из п элементы со значениями А0 ... Ап−1, и целевое значение Т, следующее подпрограмма использует мультипликативный двоичный поиск, чтобы найти индекс Т в А.
- Набор я до 0
- если я ≥ п, поиск завершается неудачно.
- еслия = Т, поиск завершен; возвращаться я.
- еслия < Т, набор я до 2 ×я + 1 и перейти к шагу 2.
- еслия > Т, набор я до 2 ×я + 2 и переходите к шагу 2.
Смотрите также
- Дерево двоичного поиска - Структура данных в виде дерева, отсортированная для быстрого поиска
- Способы хранения двоичных деревьев
- Анентафель - Генеалогическая система нумерации для перечисления прямых предков человека
Цитаты
- ^ Стэндиш, Томас А. (1980). «Глава 4.2.2: Поиск по упорядоченной таблице». Методы структуры данных. Эддисон-Уэсли. стр.136–141. ISBN 978-0201072563.
- ^ Сэйл, Роджер А. (17 июня 2008 г.). «Анализ супероптимизатора при генерации кода с несколькими ветвями» (PDF). Материалы саммита разработчиков GCC: 103–116. Получено 4 марта 2017.
- ^ Спулер, Дэвид А. (январь 1994 г.). Генерация кода компилятора для выражений многосторонних переходов как задача статического поиска (Технический отчет). Департамент компьютерных наук, Университет Джеймса Кука, Австралия. 94/03.