LeetCode Find First and Last Position of Element in Sorted Array Solution
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]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
Problem Link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Solution
We want to find two positions, first_pos
and last_pos
of the target
in nums
.
For the first_pos
, we want to find the leftmost target
. So we will do binary search on nums
,
and whenever we find target
, we search for its left side to see whether there is another target
on the left while keeping track of the leftmost seen first_pos
.
Similarly, we want to find the rightmost target
in nums
to be last_pos
.
So when we see a target
, we search for its right side and record the last_pos = current index
.
If the current element is not target
, then ordinary binary search will lead us to the correct searching side.
1def searchRange(self, nums, target):
2 left, right = 0, len(nums)-1
3 first_pos, last_pos = -1, -1
4
5 # find first pos
6 while left <= right:
7 mid = (left + right) // 2
8 if nums[mid] == target:
9 first_pos = mid
10 right = mid - 1
11 elif nums[mid] > target:
12 right = mid - 1
13 else:
14 left = mid + 1
15
16 #find last pos
17 left, right = 0, len(nums)-1
18 while left <= right:
19 mid = (left + right) // 2
20 if nums[mid] == target:
21 last_pos = mid
22 left = mid+1
23 elif nums[mid] > target:
24 right = mid - 1
25 else:
26 left = mid + 1
27 return (first_pos, last_pos)