34. Find First and Last Position of Element in Sorted Array
Содержание
Given 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]
Code
Idea:
- Find
targetindex (target_index) using Binary Search- If not exist then return
[-1, -1] - If exist then goto step 2
- If not exist then return
- We got the middle index. For now this is the most left and most right index.
- Divide
numsinto two arrays:left_numsandright_nums:- left_nums = nums[0:target_index]
- right_nums = nums[target_index:]
- Find the most left
targetinleft_nums. (Set right border in subarray) - Find the most right
targetinright_nums. (Set left border in subarray)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def find_target():
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def find_most_left(right_idx):
l = 0
r = right_idx
while l <= r:
m = (l + r) // 2
if nums[m] < target:
l = m + 1
else:
r = m - 1
return l
def find_most_right(left_idx):
l = left_idx
r = len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target: # ex: [8, 8, 8, 9, 10]
l = l + 1
else: # ex: [8, 8, 8, 9, 10]
r = m - 1
return l - 1
target_idx = find_target()
if target_idx == -1:
return [-1,-1]
left = find_most_left(target_idx)
right = find_most_right(target_idx)
return [left, right]
Code Ver2
Use prebuilt Python functions:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = bisect_left(nums, target)
if l == len(nums) or nums[l] != target:
return -1, -1
r = bisect_right(nums, target) - 1
return l, r
