测试目标存在时的测试数组大小 线性平均时间(s)二分平均时间(s)速度比(线性/二分)100.0186740.0199050.94200.0293830.0274001.07500.0603070.0324181.861000.1106540.0390882.832000.2103500.0445794.725000.5175960.05127010.1010001.0342850.05740018.0220002.1101800.06327733.35Time limit exceeded源代码-- 线性查找localfunctionlinear_search(arr,target)fori1,#arrdoifarr[i]targetthenreturniendendreturnnilend-- 二分查找迭代使用 // 整数除法localfunctionbinary_search(arr,target)localleft,right1,#arrwhileleftrightdolocalmid(leftright)//2-- Lua 5.3 整数除法localmid_valarr[mid]ifmid_valtargetthenreturnmidelseifmid_valtargetthenleftmid1elserightmid-1endendreturnnilend-- 生成有序数组localfunctiongenerate_sorted_array(size)localarr{}fori1,sizedoarr[i]i*2-- 生成步长为2的递增序列方便测试存在/不存在endreturnarrend-- 基准测试函数-- param sizes: 要测试的数组大小列表-- param trials_per_size: 每个大小下的查找次数用于平均-- param use_existing_target: true 表示目标值存在取数组中间值false 表示目标值不存在localfunctionbenchmark(sizes,trials_per_size,use_existing_target)print(数组大小\t线性平均时间(s)\t二分平均时间(s)\t速度比(线性/二分))for_,sizeinipairs(sizes)dolocalarrgenerate_sorted_array(size)localtargetifuse_existing_targetthentargetarr[math.floor(size/2)1]-- 存在元素elsetargetsize*21-- 不存在元素end-- 测试线性查找localstartos.clock()for_1,trials_per_sizedolinear_search(arr,target)endlocallinear_timeos.clock()-start-- 测试二分查找localstartos.clock()for_1,trials_per_sizedobinary_search(arr,target)endlocalbinary_timeos.clock()-startlocalratiolinear_time/binary_timeprint(string.format(%d\t\t%.6f\t\t%.6f\t\t%.2f,size,linear_time,binary_time,ratio))endend-- 定义要测试的数组大小对数增长localsizes{10,20,50,100,200,500,1000,2000,5000,10000,20000,50000,100000}localtrials_per_size100000-- 每个大小重复查找次数保证统计稳定性print( 目标存在时的测试 )benchmark(sizes,trials_per_size,true)print(\n 目标不存在时的测试 )benchmark(sizes,trials_per_size,false)