#34 Find First and Last Position of Element in Sorted Array——Top 100 Liked Questions

矫情吗；* 2022-02-01 15:51 132阅读 0赞

Given an array of integers `nums` sorted in ascending order, find the starting and ending position of a given `target` value.

Your algorithm's runtime complexity must be in the order of *O*(log *n*).

If the target is not found in the array, return `[-1, -1]`.

**Example 1:**

Input: nums = [5,7,7,8,8,10], target = 8
    Output: [3,4]

**Example 2:**

Input: nums = [5,7,7,8,8,10], target = 6
    Output: [-1,-1]

> """
> 
> 第一次：基本思想是利用二叉搜索：搜索target是否等于nums\[mid\]。当target=nums\[mid\]时，再分两种情况：找一下mid的左边部分是否有等于target的，再找一下mid右边是否有等于target的；当target<nums\[mid\]，right=mid-1；当target>nums\[mid\]，left=mid+1；
> 
> 最后对res结果集进行判断，当res为空时，返回\[-1, -1\]；当res只有一个值时，对值进行复制；当res中有多个值时，返回最小和最大值，即为target出现的初始和结束的位置
> 
> 代码太啰嗦
> 
> """
> 
>     class Solution(object):
>         def searchRange(self, nums, target):
>             """
>             :type nums: List[int]
>             :type target: int
>             :rtype: List[int]
>             """
>             if len(nums) == 0 or target is None:
>                 return [-1, -1]
>             left = 0
>             right = len(nums) - 1
>             res = []
>             while left <= right:
>                 mid = (left + right) // 2
>                 if target == nums[mid]:
>                     res.append(mid)
>                     i = 1
>                     j = 1
>                     for i in range(1, mid + 1):
>                         if mid > 0 and target == nums[mid - i]:
>                             res.append(mid - i)
>                     for j in range(1, len(nums) - mid):
>                         if mid + 1 < len(nums) and target == nums[mid + j]:
>                             res.append(mid + j)
>                     break
>                 elif target < nums[mid]:
>                     right = mid - 1
>                 else:
>                     left = mid + 1
>     
>             if len(res) == 1:
>                 return res * 2
>             elif len(res) == 0:
>                 return [-1, -1]
>             elif len(res) == 2:
>                 return sorted(res)
>             else:
>                 return [min(res), max(res)]
> 
> """
> 
> Runtime: 76 ms, faster than 40.07% of Python online submissions for Find First and Last Position of Element in Sorted Array.
> 
> Memory Usage: 13 MB, less than 5.30% of Python online submissions for Find First and Last Position of Element in Sorted Array.
> 
> """