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!"