Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
0

Interpolation Search Error?

Asked by 10 years ago

Here is my code:

local function interpolateSearch(array,toFind)
local low = 1
local high = #array
local mid
while array[low] <= toFind and array[high] >= toFind do
mid = low +((toFind-array[low])*(high-low))/(array[high]-array[low])
if array[mid] < toFind then
low = mid + 1
elseif array[mid] > toFind then
high = mid - 1
else
return mid
end
end
if array[low] == toFind then
return low
else
return -1
end
end

it works fine if toFind is set as a number in array, but if toFind is set as a number not in the array I get the following error: (I'm not compiling in roblox studio so the error message is a little different)

attempt to compare nil with number stack traceback: t.lua:7: in function 'interpolateSearch' t.lua:23: in main chunk [C]: ?

I am using the java sample implementation for reference at http://en.wikipedia.org/wiki/Interpolation_search

1 answer

Log in to vote
0
Answered by 10 years ago

Nvm. I found out how to do it at http://lua-users.org/wiki/InterpolatingSearch

Ad

Answer this question