Multiplicative binary search
id:
multiplicative-binary-search-206-16945288
title:
Multiplicative binary search
text:
In computer science, multiplicative binary search is a variation
of binary search that uses a specific permutation of keys in an array instead of the sorted order used by regular binary
search.
Multiplicative binary search was first described by Thomas Standish in 1980.
This algorithm was originally proposed to simplify the midpoint index calculation on small computers without efficient division or shift operations.
On modern hardware, the cache-friendly nature of multiplicative binary search ma
brand slug:
wiki
category slug:
encyclopedia
description:
Binary search variation with simplified midpoint calculation
original url:
https://en.wikipedia.org/wiki/Multiplicative_binary_search
date created:
2017-03-05T01:05:23Z
date modified:
2024-09-10T20:38:09Z
main entity:
{"identifier":"Q29033062","url":"https://www.wikidata.org/entity/Q29033062"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/3/3b/Multiplicative_Binary_Search_Depiction.svg","width":470,"height":200}
fields total:
13
integrity:
16