bisect

Chris Wu · Chris Wu · commit ecf16ce247b1 · 2019-08-04T16:56:43.000+08:00
diff --git a/problems/binary-search.py b/problems/binary-search.py
@@ -9,6 +9,8 @@
 Continue this proccess, until we find the value.
 
 If we can't find the value, then `l` and `r` are going to collapse. `return -1`
+
+Another solution is to use [bisect](https://docs.python.org/2.7/library/bisect.html).
 """
 class Solution(object):
     def search(self, nums, target):
@@ -28,3 +30,15 @@ def search(self, nums, target):
             else:
                 l = p+1
         return -1
+
+import bisect
+class Solution(object):
+    def search(self, nums, target):
+        if nums is None or len(nums)==0: return -1
+        if target<nums[0] or nums[-1]<target: return -1 #check if out of range
+
+        i = bisect.bisect_left(nums, target)
+
+        #check if target in `nums`
+        if nums[i]==target: return i
+        else: return -1
diff --git a/problems/find-first-and-last-position-of-element-in-sorted-array.py b/problems/find-first-and-last-position-of-element-in-sorted-array.py
@@ -9,6 +9,8 @@
 Second, we move pointers, `l`, `r` to find the right-most and left-most targets.
 
 The time complexity is O(LogN), becuase we use the concept of binary search to find the `target`.
+
+Another solution is to use [bisect](https://docs.python.org/2.7/library/bisect.html).
 """
 class Solution(object):
     def searchRange(self, nums, target):
@@ -33,3 +35,16 @@ def searchRange(self, nums, target):
         while 0<=l-1 and nums[l-1]==target:
             l = l-1
         return [l, r]
+
+
+import bisect
+class Solution(object):
+    def searchRange(self, nums, target):
+        if nums is None or len(nums)==0: return [-1, -1]
+        if target<nums[0] or nums[-1]<target: return [-1, -1] #check if target out of range
+        l = bisect.bisect_left(nums, target)
+        r = bisect.bisect_right(nums, target)
+
+        if nums[l]!=target or nums[r-1]!=target: return [-1, -1] #check if target in `nums`
+        return [l, r-1]
+
