Find First and Last Position of Element in Sorted Array
1 min readJan 26, 2021
Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
Follow up: Could you write an algorithm with O(log n)
runtime complexity?
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]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Analysis:
二分法找中间数,然后trace到第一个和最后一个。
improve:
两个二分法找lower和upper bound
Solution:
class Solution(object):
def searchRange(self, nums, target):
“””
:type nums: List[int]
:type target: int
:rtype: List[int]
“””
if not nums: return [-1, -1]
def lowerBound(nums, target):
i, j = 0, len(nums)
while i<j:
mid = (i+j)/2
if nums[mid] >= target:
j = mid
else:
i = mid + 1
return i
def higherBound(nums, target):
i, j = 0, len(nums)
while i<j:
mid = (i+j)/2
if nums[mid] > target:
j = mid
else:
i = mid + 1
return i
lower = lowerBound(nums, target)
higher = higherBound(nums, target)-1
if lower == len(nums) or nums[lower]!=target:
return [-1, -1]
return [lower, higher]