Multiplicative binary search: Difference between revisions

Revision as of 14:57, 22 May 2020

Revision as of 08:15, 19 February 2022

Line 11:

|best-time=[[big O notation#Orders of common functions|''O''(1)]]

|average-time=[[big O notation#Orders of common functions|''O''(log ''n'')]]

|optimal=Yes

}}

In [[computer science]], '''multiplicative binary search''' (also known as '''Eyztinger binary search'''<ref>{{cite journal |first1=Paul-Virak |last1=Khuong |first2=Pat |last2=Morin |title=Array Layouts for Comparison-Based Searching |journal=ACM Journal of Experimental Algorithmics |volume=22 |issue=1.3 |pages=1-39 |year=2017 |doi=10.1145/3053370 |url=https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf}}</ref><ref>{{cite web |first=Sergey |last=Slotkin |title=Eytzinger Binary Search |website=Algorithmica |date= March 2020 |url=https://algorithmica.org/en/eytzinger}}</ref>) is a variation

In [[computer science]], '''multiplicative binary search''' is a variation

of [[binary search algorithm|binary search]] that uses a specific permutation of keys in an array instead of the sorted order used by regular binary

search.<ref>{{cite book|first=Thomas A.|last=Standish|title=Data Structure Techniques|url=https://archive.org/details/datastructuretec0000stan|url-access=registration|publisher=Addison-Wesley|year=1980|chapter=Chapter 4.2.2: Ordered Table Search|pages=[https://archive.org/details/datastructuretec0000stan/page/136 136–141]|isbn=978-0201072563}}</ref>

Line 37 ⟶ 36:

* {{SDlink|Binary search tree}}

* {{SDlink|Binary_tree#Methods_for_storing_binary_trees|Methods for storing binary trees}}

* {{SDlink|Ahnentafel}} developed by [[Michaël Eytzinger]] in 1590.

== Citations ==