1def assert_equals(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5class Solution
 6  # time: O(n)
 7  def self.run(items, target)
 8    first = -1
 9    last = -1
10
11    for i in (0..target.size)
12      item = items[i]
13      if item == target
14        first = i if first == -1
15        last = i
16      end
17    end
18
19    [first, last]
20  end
21
22  # time: O(n)
23  def self.run(items, target)
24    first = last = -1
25    min, max = 0, (items.size - 1)
26
27    while min < max
28      mid = (min + max) / 2
29      item = items[mid]
30
31      if item == target
32        i = mid
33        i-=1 while items[i] == target && i > 0
34        first = i + 1
35
36        i = mid
37        i+=1 while items[i] == target && i < items.size
38        last = i - 1
39        break
40      elsif target < item
41        max = mid
42      else
43        min = mid + 1
44      end
45    end
46
47    [first, last]
48  end
49end
50
51=begin
52mid = 5
53first = -1
54last = -1
55
56                  x
57|1|3|3|5|7|8 |9|9|9|15|
58=end
59
60assert_equals(Solution.run([1,3,3,5,7,8,9,9,9,15], 9), [6, 8])
61assert_equals(Solution.run([100, 150, 150, 153], 150), [1, 2])
62assert_equals(Solution.run([1,2,3,4,5,6,10], 9), [-1, -1])
63assert_equals(Solution.run([1, 2, 2, 2, 2, 3, 4, 7, 8, 8], 2), [1, 4])
64puts "Yay!"