34. Find First and Last Position

思路: 写两个函数，分别用于寻找第一个index和最后一个index,搜索方法用二分法查找即可。
注意点: 如果查找到nums[mid] == target，要注意分两种情况，一种是找到当前index就是要查找的位置，另一种是需要继续二分查找。

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start = self.findstart(nums, target)
        end = self.findend(nums, target)
        return [start, end]

    def findstart(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            # 如果nums[mid] == target,分两种情况,如果mid是0或者mid之前的元素不为target,直接return mid
            # 否则,说明应该去mid的左边去搜索
            if nums[mid] == target:
                if mid == 0 or nums[mid - 1] != target:
                    return mid
                else:
                    right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1


    def findend(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                if mid == len(nums) - 1 or nums[mid + 1] != target:
                    return mid
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

s = Solution()
res = s.searchRange([5,7,7,8,8,10], 8)
print(res)