/
ch-2.lua
executable file
·40 lines (34 loc) · 1.02 KB
/
ch-2.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
local t2 = {}
t2.DEFAULT_INPUT = {{1, 2, 3, 4}, 3}
function t2.binary_search(coll, n, startp, endp)
if endp >= startp then
local mid = startp + (endp - startp) // 2
local v = coll[mid]
if v == n then
return mid
elseif v > n then
return t2.binary_search(coll, n, startp, mid - 1)
else
return t2.binary_search(coll, n, mid + 1, endp)
end
else
return -1 * startp - 1
end
end
function t2.search_insert_position(coll, n)
local index = t2.binary_search(coll, n, 1, #coll)
-- Lua's tables are 1-indexed, hence we need to account for that in both
-- cases, both when the result is negative (meaning the number isn't in the
-- list, and when the result is positive, indicating the number was found.
if index < 0 then
return -1 * index - 2
else
return index - 1
end
end
function t2.run(_)
local ns, n
ns, n = table.unpack(t2.DEFAULT_INPUT)
print(t2.search_insert_position(ns, n))
end
return t2