34. Search for a Range
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]
Solution
(1) Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] rst = new int[2];
Arrays.fill(rst, -1);
if (nums == null || nums.length == 0) {
return rst;
}
int start = 0;
int end = nums.length-1;
while (start < end) {
int mid = start + (end-start)/2;
if (nums[mid] >= target) {
end = mid;
} else {
start = mid+1;
}
}
if (nums[start] == target) {
rst[0] = start;
} else {
return rst;
}
start = 0;
end = nums.length-1;
while(start < end) {
int mid = start+(end-start+1)/2;
if (nums[mid] <= target ) {
start = mid;
} else {
end = mid -1;
}
}
if (nums[end] == target) {
rst[1] = end;
return rst;
}
rst[0] = -1;
return rst;
}
}
(2) Python
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1, -1]
rst = []
start, end = 0, len(nums)-1
while start < end:
mid = int(start+(end-start)/2)
if nums[mid] >= target:
end = mid
else:
start = mid+1
if nums[start] == target:
rst.append(start)
else:
return [-1, -1]
start, end = 0, len(nums)-1
while start < end:
mid = int(start+(end-start+1)/2)
if nums[mid] <= target:
start = mid
else:
end = mid-1
if nums[end] == target:
rst.append(end)
return rst
return [-1, -1]
(3) Scala