Module:Exponential search explained

-- This module provides a generic exponential search algorithm.requirestrict

local checkType = require('libraryUtil').checkTypelocal 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) endend

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