https://the-democratika.com/wiki/index.php?action=history&feed=atom&title=Module%3AExponential_search
Module:Exponential search - Revision history
2026-04-04T11:12:36Z
Revision history for this page on the wiki
MediaWiki 1.43.0
https://the-democratika.com/wiki/index.php?title=Module:Exponential_search&diff=6157&oldid=prev
>Uzume: strict
2023-02-10T20:10:53Z
<p>strict</p>
<p><b>New page</b></p><div>-- This module provides a generic exponential search algorithm.<br />
require[[strict]]<br />
<br />
local checkType = require('libraryUtil').checkType<br />
local floor = math.floor<br />
<br />
local function midPoint(lower, upper)<br />
return floor(lower + (upper - lower) / 2)<br />
end<br />
<br />
local function search(testFunc, i, lower, upper)<br />
if testFunc(i) then<br />
if i + 1 == upper then<br />
return i<br />
end<br />
lower = i<br />
if upper then<br />
i = midPoint(lower, upper)<br />
else<br />
i = i * 2<br />
end<br />
return search(testFunc, i, lower, upper)<br />
else<br />
upper = i<br />
i = midPoint(lower, upper)<br />
return search(testFunc, i, lower, upper)<br />
end<br />
end<br />
<br />
return function (testFunc, init)<br />
checkType('Exponential search', 1, testFunc, 'function')<br />
checkType('Exponential search', 2, init, 'number', true)<br />
if init and (init < 1 or init ~= floor(init) or init == math.huge) then<br />
error(string.format(<br />
"invalid init value '%s' detected in argument #2 to " ..<br />
"'Exponential search' (init value must be a positive integer)",<br />
tostring(init)<br />
), 2)<br />
end<br />
init = init or 2<br />
if not testFunc(1) then<br />
return nil<br />
end<br />
return search(testFunc, init, 1, nil)<br />
end</div>
>Uzume