LeetCode Problem
34. Find First and Last Position of Element in Sorted Array
Link to LeetCode
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]
// We can first find the start and then the end of the target.
public int[] searchRange(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while(l< r){
int m=l+(r-l)/2;
if(nums[m]< target){
l=m+1;
}else{
r=m;
}
}
int first=l;
if(l < nums.length&&nums[l]==target){//l is in boundary and is the target
l=0;
r=nums.length-1;
while(l< r){
int m=l+(r-l+1)/2;
if(nums[m]>target){
r=m-1;
}else{
l=m;
}
}
return new int[]{first, r};
}
return new int[]{-1,-1};
}