The challenge
Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
Follow up: Could you 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 <= 10<sup>5</sup>
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
nums
is a non-decreasing array.-10<sup>9</sup> <= target <= 10<sup>9</sup>
The solution in Java code
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = -1, last = -1;
for (int i=0; i<nums.length; i++) {
if (nums[i]==target) first = i;
continue;
}
for (int i=nums.length-1; i>=0; i--) {
if (nums[i]==target) last = i;
continue;
}
return new int[] {last, first};
}
}