Problem
34. Find First and Last Position of Element in Sorted Array
Left boundary
int findFirst(int[] nums, int target) {
int left = 0, right = n - 1, mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
// attention (1)
right = mid - 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
lo = mid + 1;
}
}
//attention (2)
return left < n && nums[left] == target ? left: -1;
}Attention
To find the first position of the target
- when one position is found, we need to move our search space to the left.
- After the loop finishes, we need to check
leftis a valid index of the original array.- The element at
leftis equal totarget.
Right boundary
int findLast(int[] nums, int target) {
int left = 0, right = n - 1, mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
// attention (1)
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
lo = mid + 1; }
}
// attention (2)
return right < 0 && nums[right] == target ? right: -1;
}Attention
To find the last position of the target
- when one position is found, we need to move our search space to the right.
- After the loop finishes, we need to check
rightis a valid index of the original array.- The element at
rightis equal totarget.