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
|
def assert_equals(x, y)
raise [x, y].inspect unless x == y
end
class Solution
# time: O(n)
def self.run(items, target)
first = -1
last = -1
for i in (0..target.size)
item = items[i]
if item == target
first = i if first == -1
last = i
end
end
[first, last]
end
# time: O(n)
def self.run(items, target)
first = last = -1
min, max = 0, (items.size - 1)
while min < max
mid = (min + max) / 2
item = items[mid]
if item == target
i = mid
i-=1 while items[i] == target && i > 0
first = i + 1
i = mid
i+=1 while items[i] == target && i < items.size
last = i - 1
break
elsif target < item
max = mid
else
min = mid + 1
end
end
[first, last]
end
end
=begin
mid = 5
first = -1
last = -1
x
|1|3|3|5|7|8 |9|9|9|15|
=end
assert_equals(Solution.run([1,3,3,5,7,8,9,9,9,15], 9), [6, 8])
assert_equals(Solution.run([100, 150, 150, 153], 150), [1, 2])
assert_equals(Solution.run([1,2,3,4,5,6,10], 9), [-1, -1])
assert_equals(Solution.run([1, 2, 2, 2, 2, 3, 4, 7, 8, 8], 2), [1, 4])
puts "Yay!"
|
