Module:Exponential search: Difference between revisions
imported>Uzume (strict) |
1>Xiplus-abot m (已更改“Module:Exponential search”的保护设置：高風險模板：121389引用<!-- 機器人3 -->（[编辑=仅允许管理员]（无限期）[移动=仅允许管理员]（无限期））) |
||
| Line 1: | Line 1: | ||
-- This module provides a generic exponential search algorithm. | -- This module provides a generic exponential search algorithm. | ||
local checkType = require('libraryUtil').checkType | local checkType = require('libraryUtil').checkType | ||
| Line 33: | Line 32: | ||
if init and (init < 1 or init ~= floor(init) or init == math.huge) then | if init and (init < 1 or init ~= floor(init) or init == math.huge) then | ||
error(string.format( | error(string.format( | ||
" | "无效的初始值 '%s' 在参数 #2 中检测到" .. | ||
"'Exponential search' | "'Exponential search'（初始值必须是正整数）", | ||
tostring(init) | tostring(init) | ||
), 2) | ), 2) | ||
Revision as of 20:51, 26 March 2025
-- 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') checkType('Exponential search', 2, init, 'number', true) if init and (init < 1 or init ~= floor(init) or init == math.huge) then error(string.format( "无效的初始值 '%s' 在参数 #2 中检测到" .. "'Exponential search'（初始值必须是正整数）", tostring(init) ), 2) end init = init or 2 if not testFunc(1) then return nil end return search(testFunc, init, 1, nil) end