-- Time Complexity O(n)
local function linear_search(items, x)
for index, item in ipairs(items) do
if item == x then
return index
end
end
-- Not found: nil, positions start at 1
return nil
end
local items = {2, 3, 5, 7, 11, 13, 17}
local index_1 = linear_search(items, 1)
-- index_1 = nil
local index_7 = linear_search(items, 7)
-- index_7 = 4
local index_19 = linear_search(items, 19)
-- index_19 = nil
print("index_1 = " .. tostring(index_1))
print("index_7 = " .. tostring(index_7))
print("index_19 = " .. tostring(index_19))
-- *** simplified speed test ***
items = {}
for n = 1, 1000000 do
items[n] = n
end
local count = 10
local start = os.clock()
for _ = 1, count do
linear_search(items, 777777)
end
local elapsed = os.clock() - start
local microseconds = elapsed / count * 1e6
-- The time depends on the machine
print(string.format("microseconds = %.2f",
microseconds))