## linear search

in lua

linear, search

### Source Code

``````-- Linear search algorithm implementation
-- See: http://en.wikipedia.org/wiki/Linear_search

-- Recursive search helper
local function recurse_search(t, v, i, s)
if t[i] == nil then return nil end
if t[i] == v then return i end
return recurse_search(t, v, i + s, s)
end

-- Performs a search by incrementing upward a search index
-- list    : the list where to search
-- item    : the value to be searched
-- returns : the value index hen found, nil otherwise.
local function forward_iteration(list, item)
for i, value in ipairs(list) do
if item == value then return i end
end
end

-- Performs a recursive search by incrementing upward a search index
-- list    : the list where to search
-- item    : the value to be searched
-- returns : the value index hen found, nil otherwise.
local function recursive_search(list, item)
return recurse_search(list, item, 1, 1)
end

-- Performs a search by incrementing downward a search index
-- list    : the list where to search
-- item    : the value to be searched
-- returns : the value index hen found, nil otherwise.
local function backward_iteration(list, item)
for i = #list, 1, -1 do
local value = list[i]
if item == value then return i end
end
end

-- Performs a recursive search by incrementing downward a search index
-- list    : the list where to search
-- item    : the value to be searched
-- returns : the value index hen found, nil otherwise.
local function reverse_recursive_search(list, item)
return recurse_search(list, item, #list, -1)
end

return {
forward = forward_iteration,
backward = backward_iteration,
recursive = recursive_search,
backward_recursive = reverse_recursive_search,
}
``````
``````-- Tests for linear_search.lua
local search = require 'linear_search'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

local t1 = {'a', 'b', 'c', 'd', 'e', 'f'}
local t2 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
local t3 = {false, true, 'false', 'true'}

run('Forward iteration search', function()
assert(search.forward(t1, 'd')     == 4)
assert(search.forward(t1, 'g')     == nil)
assert(search.forward(t2, 8)       == 8)
assert(search.forward(t2, '3')     == nil)
assert(search.forward(t3, 'false') == 3)
assert(search.forward(t3, nil)     == nil)
end)

run('Backward iteration search', function()
assert(search.backward(t1, 'd')     == 4)
assert(search.backward(t1, 'g')     == nil)
assert(search.backward(t2, 8)       == 8)
assert(search.backward(t2, '3')     == nil)
assert(search.backward(t3, 'false') == 3)
assert(search.backward(t3, nil)     == nil)
end)

run('Recursive iteration search', function()
assert(search.recursive(t1, 'd')     == 4)
assert(search.recursive(t1, 'g')     == nil)
assert(search.recursive(t2, 8)       == 8)
assert(search.recursive(t2, '3')     == nil)
assert(search.recursive(t3, 'false') == 3)
assert(search.recursive(t3, nil)     == nil)
end)

run('Reverse recursive iteration search', function()
assert(search.backward_recursive(t1, 'd')     == 4)
assert(search.backward_recursive(t1, 'g')     == nil)
assert(search.backward_recursive(t2, 8)       == 8)
assert(search.backward_recursive(t2, '3')     == nil)
assert(search.backward_recursive(t3, 'false') == 3)
assert(search.backward_recursive(t3, nil)     == nil)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````