Update search-for-a-range.py

kamyu104 · kamyu104 · commit 8367b081a815 · 2015-04-19T16:15:34.000+08:00
diff --git a/Python/search-for-a-range.py b/Python/search-for-a-range.py
@@ -17,22 +17,34 @@ class Solution:
     # @param target, an integer to be searched
     # @return a list of length 2, [index1, index2]
     def searchRange(self, A, target):
-        left = self.binarySearch(lambda x, y: x > y, A, target)
+        # Find the first index where target <= A[idx]
+        left = self.binarySearch(lambda x, y: x <= y, A, target)
         if left >= len(A) or A[left] != target:
             return [-1, -1]
-        right = self.binarySearch(lambda x, y: x >= y, A, target)
+        # Find the first index where target < A[idx]
+        right = self.binarySearch(lambda x, y: x < y, A, target)
         return [left, right - 1]
     
     def binarySearch(self, compare, A, target):
         start, end = 0, len(A)
         while start < end:
             mid = start + (end - start) / 2
             if compare(target, A[mid]):
+                end = mid
+            else:
                 start = mid + 1
+        return start
+    
+    def binarySearch2(self, compare, A, target):
+        start, end = 0, len(A) - 1
+        while start <= end:
+            mid = start + (end - start) / 2
+            if compare(target, A[mid]):
+                end = mid - 1
             else:
-                end = mid
+                start = mid + 1
         return start
 
 if __name__ == "__main__":
     print Solution().searchRange([2, 2], 3)
-    print Solution().searchRange([5, 7, 7, 8, 8, 10], 8)
+    print Solution().searchRange([5, 7, 7, 8, 8, 10], 8)
