34. Find First and Last Position of Element in Sorted Array
Medium
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
To solve the "Find First and Last Position of Element in Sorted Array" problem in Java with a Solution
class, we can follow these steps:
- Define a
Solution
class. - Define a method named
searchRange
that takes an integer arraynums
and an integertarget
as input and returns an integer array representing the starting and ending positions oftarget
innums
. Iftarget
is not found, return[-1, -1]
. - Implement binary search to find the first and last occurrences of
target
. - Set the left pointer
left
to 0 and the right pointerright
to the length ofnums
minus 1. - Initialize two variables
firstOccurrence
andlastOccurrence
to -1. - Perform two binary search operations:
- First, find the first occurrence of
target
:- While
left
is less than or equal toright
:- Calculate the middle index
mid
as(left + right) / 2
. - If
nums[mid]
is equal totarget
, updatefirstOccurrence = mid
and continue searching on the left half by updatingright = mid - 1
. - Otherwise, if
target
is less thannums[mid]
, updateright = mid - 1
. - Otherwise, update
left = mid + 1
.
- Calculate the middle index
- While
- Second, find the last occurrence of
target
:- Reset
left
to 0 andright
to the length ofnums
minus 1. - While
left
is less than or equal toright
:- Calculate the middle index
mid
as(left + right) / 2
. - If
nums[mid]
is equal totarget
, updatelastOccurrence = mid
and continue searching on the right half by updatingleft = mid + 1
. - Otherwise, if
target
is greater thannums[mid]
, updateleft = mid + 1
. - Otherwise, update
right = mid - 1
.
- Calculate the middle index
- Reset
- First, find the first occurrence of
- Return the array
[firstOccurrence, lastOccurrence]
.
Here's the implementation:
public class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int firstOccurrence = -1;
int lastOccurrence = -1;
// Find first occurrence
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
firstOccurrence = mid;
right = mid - 1;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Find last occurrence
left = 0;
right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
lastOccurrence = mid;
left = mid + 1;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return new int[]{firstOccurrence, lastOccurrence};
}
}
This implementation provides a solution to the "Find First and Last Position of Element in Sorted Array" problem in Java. It returns the starting and ending positions of target
in nums
using binary search, with a time complexity of O(log n).