Home
Random
Log in
Settings
About Arcadian Odyssey Extended Universe
Disclaimers
Arcadian Odyssey Extended Universe
Search
Editing
Module:Exponential search
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
-- This module provides a generic exponential search algorithm. require[[strict]] 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
Summary:
Please note that all contributions to Arcadian Odyssey Extended Universe may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Arcadian Odyssey Extended Universe:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)