Module:Exponential search

Documentation for this module may be created at Module:Exponential search/doc

-- This module provides a generic binary 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 binarySearch(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 binarySearch(testFunc, i, lower, upper)
	else
		upper = i
		lower = lower or 0
		i = midPoint(lower, upper)
		return binarySearch(testFunc, i, lower, upper)
	end
end

return function (testFunc, init)
	checkType('Binary search', 1, testFunc, 'function')
	checkType('Binary search', 2, initNum, 'number', true)
	if init then
		if init < 1 or init ~= floor(init) or init == math.huge or tostring(init) == '-nan' then
			error("if an init is specified to 'Binary search', it must be a positive integer", 2)
		end
	else
		init = 1
	end
	if not testFunc(1) then
		return nil
	end
	return binarySearch(testFunc, init)
end