34. Find First and Last Position of Element in Sorted Array
MediumLeetCodeGiven an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must 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]
Constraints
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order.
nums
contains only integers.target
is an integer.
How to solve the problem
Not a good solution with T = O(n)
Binary Search by splitting leftSearch and rightSearch, but not universal enough
Binary Search with the most universal approach
Code
- Approach 1: Linear Search (O(n))
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# Not a good solution with T = O(n)
pre = -1
suf = -1
for i, x in enumerate(nums):
if x == target:
pre = i
break
for i in range(len(nums)-1, -1, -1):
if nums[i] == target:
suf = i
break
return [pre, suf]
- Approach 2: Binary Search by splitting leftSearch and rightSearch, but not universal enough
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# Binary Search
# Split leftSearch and rightSearch
if not nums:
return [-1,-1]
def leftSearch(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
if left < len(nums) and nums[left] == target:
return left
else:
return -1
def rightSearch(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if right >= 0 and nums[right] == target:
return right
else:
return -1
pre = leftSearch(nums, target)
suf = rightSearch(nums, target)
return [pre, suf]
- Approach 3: Binary Search with the most universal approach
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# Binary Search with the most universal approach
start = lower_bound(nums, target)
if start >= len(nums) or nums[start] != target:
return [-1, -1]
end = lower_bound(nums, target + 1) - 1
return [start, end]
def lower_bound(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
Complexity
Time complexity: O(log n)
Space complexity: O(1)
Comments
No comments yet. Be the first to comment!