34. 在排序数组中查找元素的第一个和最后一个位置

题目分析

这个题目拆分为left_bound和right_bound比较容易理解.
虽然代码量有冗余.

class Solution(object):
    def left_bound(self, nums, target):
        low = 0
        high = len(nums)-1
        res = []
        while low<=high:
            mid = low + (high-low)/2
            if(nums[mid] < target):
                low = mid+1
            elif(nums[mid]>target):
                high = mid-1
            elif nums[mid] == target:
                if mid == 0 or nums[mid-1]<target:
                    return mid
                high = mid -1
        return -1
    
    def right_bound(self, nums, target):
        low = 0
        high = len(nums)-1
        res = []
        while low<=high:
            mid = low + (high-low)/2
            if(nums[mid] < target):
                low = mid+1
            elif(nums[mid]>target):
                high = mid-1
            elif nums[mid] == target:
                if mid == len(nums)-1 or nums[mid+1]>target:
                    return mid
                low = mid +1
        return -1
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        left = self.left_bound(nums,target)
        right = self.right_bound(nums,target)
        return [left,right]