Module:Exponential search

Module documentation[view] [edit] [history] [purge]

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.

The above documentation is transcluded from Module:Exponential search/doc. (edit | history)
Editors can experiment in this module's sandbox (create | mirror) and testcases (create) 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