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