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

1、题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

　　输入: nums = [5,7,7,8,8,10], target = 8

　　输出: [3,4]

示例 2:

　　输入: nums = [5,7,7,8,8,10], target = 6

　　输出: [-1,-1]

2、题解

2.1、解法一

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        if n == 1:
            if target == nums[0]:
                return [0,0]
            else:
                return [-1,-1]
        first,last = 0, n-1

        r_list = []
        while first <= last:

            mid = int((first + last)/2)
            print(mid)
            if nums[mid] == target:
                left,right = mid,mid+1
                while first <= left and nums[left] == target:
                    left -= 1
                print(r_list)
                while right <= last and nums[right] == target:
                    right += 1
                r_list = [left+1,right-1]
                return r_list
            elif target > nums[mid]:
                # 目标值大于中间值
                first = mid + 1
            else:
                # 目标值小于中间值
                last = mid - 1
            print(first,last)
        return [-1, -1]