3.3 Search for a Range

在线题测：https://www.lintcode.com/problem/search-for-a-range/description

在线题解：https://www.jiuzhang.com/solution/search-for-a-range/

61.搜索区间

中文

English

给定一个包含n个整数的排序数组，找出给定目标值target的起始和结束位置。

如果目标值不在数组中，则返回[-1, -1]

样例

例1:

输入:
[]
9
输出:
[-1,-1]

例2:

输入:
[5, 7, 7, 8, 8, 10]
8
输出:
[3, 4]

挑战

时间复杂度 O(logn)

代码更新如下：

class Solution:
    """
    @param A : a list of integers
    @param target : an integer to be searched
    @return : a list of length 2, [index1, index2]
    """
    def searchRange(self, A, target):
        if len(A) == 0:
            return [-1, -1]

        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if A[mid] < target:
                start = mid
            else:
                end = mid

        if A[start] == target:
            leftBound = start
        elif A[end] == target:
            leftBound = end
        else:
            return [-1, -1]

        start, end = leftBound, len(A) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if A[mid] <= target:
                start = mid
            else:
                end = mid
        if A[end] == target:
            rightBound = end
        else:
            rightBound = start
        return [leftBound, rightBound]