Medium
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]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def search_range(nums, target)
ans = [helper(nums, target, false), helper(nums, target, true)]
ans
end
private
def helper(nums, target, equals)
l = 0
r = nums.length - 1
result = -1
while l <= r
mid = l + (r - l) / 2
result = mid if nums[mid] == target
if nums[mid] < target || (nums[mid] == target && equals)
l = mid + 1
else
r = mid - 1
end
end
result
end