Search for a Range

此题有个假二分做法，也有个真二分做法，假二分是找到目标元素后左右扩展找边界，这样最坏情况就是O(n)了，真二分则做两次二分，一次找左边，一次找右边，下面只写真二分

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1, -1]

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

        left, right = 0, len(nums) - 1
        if nums[end] == target:
            right = end
        elif nums[start] == target:
            right = start
        else:
            return [-1, -1]

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

        if nums[start] == target:
            left = start
        elif nums[end] == target:
            left = end
        else:
            return [-1, -1]
        return [left, right]