Commit f603081

@@ -3,6 +3,7 @@ def assert_equals(x, y)
 end
 
 class Solution
+  # time: O(n)
   def self.run(items, target)
     first = -1
     last = -1
@@ -17,8 +18,45 @@ class Solution
 
     [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])