모듈:Exponential search

모듈 설명문서[보기] [편집] [역사] [새로 고침]

이 모듈은 일반적인 지수 탐색(exponential search) 알고리즘을 제공합니다. 이 종류의 탐색은 정렬된 배열에서 키를 찾을 때, 가능한 한 적은 배열 요소만 검사하고 싶을 때 유용할 수 있습니다. 이는 다음과 같은 상황에서 사용할 수 있습니다.

• 모든 항목이 존재하는지 확인하지 않고 아카이브 세트에서 가장 높은 아카이브 번호를 찾는 경우.
• 위키텍스트를 전개하지 않고 frame.args에서 위치 인수의 개수를 찾는 경우.

이 모듈의 자세한 설명은 en:Module:Exponential search/doc 항목을 참고하십시오.

-- 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