34. Find First and Last Position of Element in Sorted Array (Medium)
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
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]
Solutions
class Solution {
// Firstly, binary search the nums and find out one slot of equal value to target
// Next, traverse both sides from above found slot.
// Finally, work out the range of the target value
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[]{-1, -1};
if (nums == null || nums.length == 0) {
return ans;
}
int len = nums.length;
if (target < nums[0] || target > nums[len - 1]) {
return ans;
}
int start = -1;
int end = nums.length - 1;
int mid = binarySearch(nums, target);
if (mid < 0) {
return ans;
}
int left = mid - 1;
while (left >= 0 && nums[left] == target) {
left--;
}
int right = mid + 1;
while (right < len && nums[right] == target) {
right++;
}
return new int[]{left + 1, right - 1};
}
public int binarySearch(int[] nums, int target) {
int left = 0;
int high = nums.length - 1;
// [5,7,7,8,8,10] left=0, right=5, mid=2; left=3,right=5,mid=4, return.
// [5,7,7,8,9,10] left=0, right=5, mid=2; left=3,right=5,mid=4; left=3,right=3,mid=3, return.
while (left <= high) {
int mid = (left + high) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
high = mid - 1;
}
}
// not found
return -1;
}
}