Module:Exponential search: Difference between revisions
Jump to navigation
Jump to search
(Created page with "-- This module provides a generic exponential search algorithm. requirestrict local checkType = require('libraryUtil').checkType local floor = math.floor local function midPoint(lower, upper) return floor(lower + (upper - lower) / 2) end local function search(testFunc, i, lower, upper) if testFunc(i) then if i + 1 == upper then return i end lower = i if upper then i = midPoint(lower, upper) else i = i * 2 end return search(testFunc, i, low...") |
m (2 revisions imported) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
-- This module provides a generic exponential search algorithm. | -- This module provides a generic exponential search algorithm. | ||
local checkType = require('libraryUtil').checkType | local checkType = require('libraryUtil').checkType | ||
local function midPoint(lower, upper) | local function midPoint(lower, upper) | ||
return floor(lower + (upper - lower) / 2) | return math.floor(lower + (upper - lower) / 2) | ||
end | end | ||
Line 31: | Line 29: | ||
checkType('Exponential search', 1, testFunc, 'function') | checkType('Exponential search', 1, testFunc, 'function') | ||
checkType('Exponential search', 2, init, 'number', true) | checkType('Exponential search', 2, init, 'number', true) | ||
if init and (init < 1 or init ~= floor(init) or init == math.huge) then | if init and (init < 1 or init ~= math.floor(init) or init == math.huge) then | ||
error(string.format( | error(string.format( | ||
"invalid init value '%s' detected in argument #2 to " .. | "invalid init value '%s' detected in argument #2 to " .. |
Latest revision as of 22:40, 24 September 2024
This is a meta module.
This module is meant to be used only by other modules. It should not be invoked in wikitext.
This module provides a generic exponential search algorithm.
Usage
This module should be loaded with require()
.
This module was adapted from Module:Exponential search on Wikipedia.
Adaptation is noted for reference and attribution only. This module may differ from the original in function or in usage.
Adaptation is noted for reference and attribution only. This module may differ from the original in function or in usage.
The above documentation is transcluded from Module:Exponential search/doc.
Editors can experiment in this module's sandbox and testcases pages.
Subpages of this module.
Editors can experiment in this module's sandbox and testcases pages.
Subpages of this module.
-- This module provides a generic exponential search algorithm.
local checkType = require('libraryUtil').checkType
local function midPoint(lower, upper)
return math.floor(lower + (upper - lower) / 2)
end
local function search(testFunc, i, lower, upper)
if testFunc(i) then
if i + 1 == upper then
return i
end
lower = i
if upper then
i = midPoint(lower, upper)
else
i = i * 2
end
return search(testFunc, i, lower, upper)
else
upper = i
i = midPoint(lower, upper)
return search(testFunc, i, lower, upper)
end
end
return function (testFunc, init)
checkType('Exponential search', 1, testFunc, 'function')
checkType('Exponential search', 2, init, 'number', true)
if init and (init < 1 or init ~= math.floor(init) or init == math.huge) then
error(string.format(
"invalid init value '%s' detected in argument #2 to " ..
"'Exponential search' (init value must be a positive integer)",
tostring(init)
), 2)
end
init = init or 2
if not testFunc(1) then
return nil
end
return search(testFunc, init, 1, nil)
end