leetcode/34.py at main · luffykesh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
    def findFirst(self, nums, target):
        low = 0
        n = len(nums)
        high =  n-1
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                if mid == 0 or nums[mid-1]!= target:
                    return mid
                else:
                    high = mid-1
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return -1

    def findLast(self, nums,target,low):
        n = len(nums)
        high =  n-1
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                if mid == n-1 or nums[mid+1]!=target:
                    return mid
                else:
                    low = mid + 1
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return -1


    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        if n == 0:
            return -1,-1
        elif n == 1:
            if nums[0] == target:
                return 0,0
            else:
                return -1,-1

        first = self.findFirst(nums,target)
        if first == -1:
            return -1,-1
        last = self.findLast(nums, target, first)
        if last == -1:
            return first,first

        return first,last