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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
' Challenge 098
'
' TASK #2 › Search Insert Position
' Submitted by: Mohammad S Anwar
' You are given a sorted array of distinct integers @N and a target $N.
'
' Write a script to return the index of the given target if found
' otherwise place the target in the sorted array and return the index.
'
' Example 1:
' Input: @N = (1, 2, 3, 4) and $N = 3
' Output: 2 since the target 3 is in the array at the index 2.
' Example 2:
' Input: @N = (1, 3, 5, 7) and $N = 6
' Output: 3 since the target 6 is missing and should be placed at
' the index 3.
' Example 3:
' Input: @N = (12, 14, 16, 18) and $N = 10
' Output: 0 since the target 10 is missing and should be placed at
' the index 0.
' Example 4:
' Input: @N = (11, 13, 15, 17) and $N = 19
' Output: 4 since the target 19 is missing and should be placed at
' the index 4.
' insert element in array at the given position
sub insert(aN() as integer, nPos as integer, n as integer)
dim u as integer, i as integer
u=ubound(aN)
redim preserve aN(u+1)
if nPos>u then ' append
aN(u+1)=n
else ' shift all and insert
for i = u+1 to nPos step -1
aN(i)=aN(i-1)
next i
aN(nPos)=n
end if
end sub
' print list of numbers
sub print_numbers(aN() as integer)
dim sep as string, i as integer
sep="("
for i=lbound(aN) to ubound(aN)
print sep;trim(str(aN(i)));
sep=", "
next i
print ")"
end sub
' search for index of element, insert in array if not found
function search_insert(aN() as integer, n as integer) as integer
dim b as integer, t as integer, m as integer
b=lbound(aN): t=ubound(aN)
if t<b then ' empty
insert aN(), 0, n: search_insert=0
elseif n<aN(b) then ' before first
insert aN(), b, n: search_insert=b
elseif n>aN(t) then ' after last
insert aN(), t+1, n: search_insert=t+1
else
m=(t+b)/2
do while b+1<t ' bisect loop
if n=aN(m) then
search_insert=m: exit function
elseif n<aN(m) then
t=m
else
b=m
end if
m=(t+b)/2
loop
insert aN(), m+1, n: search_insert=m+1 ' not found, insert
end if
end function
' main
dim aN() as integer, i as integer, n as integer
n=val(command(1))
i=2
do while command(i)<>""
redim preserve aN(i-2)
aN(i-2)=val(command(i))
i=i+1
loop
print search_insert(aN(), n)
print_numbers aN()
|
