Difference between revisions of "Module:Exponential search"
Jump to navigation
Jump to search
imported>Mr. Stradivarius m (Mr. Stradivarius moved page Module:Binary search to Module:Exponential search without leaving a redirect: turns out binary searches are technically for bounded arrays - exponential search is a better name) |
m (1 revision imported) |
||
| (10 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | -- This module provides a generic | + | -- This module provides a generic exponential search algorithm. |
local checkType = require('libraryUtil').checkType | local checkType = require('libraryUtil').checkType | ||
| Line 8: | Line 8: | ||
end | end | ||
| − | local function | + | local function search(testFunc, i, lower, upper) |
if testFunc(i) then | if testFunc(i) then | ||
if i + 1 == upper then | if i + 1 == upper then | ||
| Line 19: | Line 19: | ||
i = i * 2 | i = i * 2 | ||
end | end | ||
| − | return | + | return search(testFunc, i, lower, upper) |
else | else | ||
upper = i | upper = i | ||
| − | |||
i = midPoint(lower, upper) | i = midPoint(lower, upper) | ||
| − | return | + | return search(testFunc, i, lower, upper) |
end | end | ||
end | end | ||
return function (testFunc, init) | return function (testFunc, init) | ||
| − | checkType(' | + | checkType('Exponential search', 1, testFunc, 'function') |
| − | checkType(' | + | 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 ~= 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 " .. | ||
| − | "' | + | "'Exponential search' (init value must be a positive integer)", |
tostring(init) | tostring(init) | ||
), 2) | ), 2) | ||
end | end | ||
| − | init = init or | + | init = init or 2 |
if not testFunc(1) then | if not testFunc(1) then | ||
return nil | return nil | ||
end | end | ||
| − | return | + | return search(testFunc, init, 1, nil) |
end | end | ||
Latest revision as of 14:33, 9 March 2020
Documentation for this module may be created at Module:Exponential search/doc
-- This module provides a generic exponential search algorithm.
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, 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 ~= 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
