モジュール:Exponential search

このモジュールについての説明文ページを モジュール:Exponential search/doc に作成できます

 1 -- This module provides a generic exponential search algorithm.
 2 require[[strict]]
 3 
 4 local checkType = require('libraryUtil').checkType
 5 local floor = math.floor
 6 
 7 local function midPoint(lower, upper)
 8 	return floor(lower + (upper - lower) / 2)
 9 end
10 
11 local function search(testFunc, i, lower, upper)
12 	if testFunc(i) then
13 		if i + 1 == upper then
14 			return i
15 		end
16 		lower = i
17 		if upper then
18 			i = midPoint(lower, upper)
19 		else
20 			i = i * 2
21 		end
22 		return search(testFunc, i, lower, upper)
23 	else
24 		upper = i
25 		i = midPoint(lower, upper)
26 		return search(testFunc, i, lower, upper)
27 	end
28 end
29 
30 return function (testFunc, init)
31 	checkType('Exponential search', 1, testFunc, 'function')
32 	checkType('Exponential search', 2, init, 'number', true)
33 	if init and (init < 1 or init ~= floor(init) or init == math.huge) then
34 		error(string.format(
35 			"invalid init value '%s' detected in argument #2 to " ..
36 			"'Exponential search' (init value must be a positive integer)",
37 			tostring(init)
38 		), 2)
39 	end
40 	init = init or 2
41 	if not testFunc(1) then
42 		return nil
43 	end
44 	return search(testFunc, init, 1, nil)
45 end