Linear search

-- 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))