Search for a Range

发表于 | 分类于

[Leetcode] Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解题思路：
该题要求时间复杂度要在O(logn)内，所以使用折半查找法，在查找到对应的位置后，需要在该位置前后去查找相同的值。

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
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if nums == None or len(nums) == 0 or target < nums[0] or target > nums[-1]:
            return [-1,-1]

        l = 0
        r = len(nums) -1
        return self.helper(l, r, nums, target)

    def helper(self, l, r, nums, target):
        if l <= r:
            m = (l + r)/2
            if nums[m] == target:
                i1 = m
                i2 = m
                while(i1-1 >=l and nums[i1-1] == target):
                    i1 -=1
                while(i2+1 <len(nums) and nums[i2+1] == target):
                    i2 +=1
                return [i1,i2]
            elif nums[m] > target:
                return self.helper(l, m-1, nums, target)
            else:
                return self.helper(m+1, r, nums, target)

        else:
            return [-1,-1]