Module:Exponential search

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')
	if not testFunc(1) then
		return nil
	end
	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 values must be a positive integer)",
			tostring(init)
		), 2)
	end
	init = init or 2
	return search(testFunc, init, 1, nil)
end