原题

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]

给出[5, 7, 7, 8, 8, 10]和目标值 target=8,
返回[3, 4]

解题思路

• 错误思路：找到一个target，然后向前向后搜索边界，如果整个数组都是target，则时间复杂度变为O(n)
• 正确思路：分两步，找到target的first position和last position
• 类似的题，一个sorted array中target出现了几次，一样的解法

完整代码

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 not A or target > A[-1] or target < A[0]:
            return [-1, -1]
            
        # find left bound
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 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]
            
        # find right bound
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if A[mid] > target:
                end = mid
            else:
                start = mid
        if A[end] == target:
            rightBound = end
        elif A[start] == target:
            rightBound = start
        else:
            return [-1, -1]
            
        return [leftBound, rightBound]