search for a range

发表于 | 分类于 ， | 阅读次数 | 
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
54
55
56
57
58
59
60
61
62
63
64
65
66
"""
https://leetcode.com/problems/search-for-a-range/description/
"""

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        >>> s = Solution()
        >>> s.searchRange([5, 7, 7, 8, 8, 10], 8)
        [3, 4]
        >>> s.searchRange([5, 7, 7, 8, 8, 10], 6)
        [-1, -1]
        >>> s.searchRange([], 0)
        [-1, -1]
        >>> s.searchRange([1], 1)
        [0, 0]
        >>> s.searchRange([1, 3], 1)
        [0, 0]
        >>> s.searchRange([1, 4], 4)
        [1, 1]
        >>> s.searchRange([2, 2], 2)
        [0, 1]
        """
        start = 0
        end = len(nums)
        if end == 0:
            return [-1, -1]
        ex = -1
        while True:
            if end - start == 1:
                if nums[start] == target:
                    ex = start
                break
            mid_ind = (start+end)//2
            mid = nums[mid_ind]
            if mid > target:
                end = mid_ind
            elif mid < target:
                start = mid_ind
            else:
                ex = mid_ind
                break
        # cannot find target in nums.
        if ex == -1:
            return [-1, -1]

        start = ex
        end = ex

        # extend to the end.
        for idx in range(ex+1, len(nums)):
            if nums[idx] == target:
                end = idx
            else:
                break
        # extend to the start.
        for idx in range(ex-1, -1, -1):
            if nums[idx] == target:
                start = idx
            else:
                break
        
        return [start, end]