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 -
numsis a non-decreasing array. -
-109 <= target <= 109
SOLUTION:
class Solution:
def search(self, nums, target, cmp, ncmp):
beg = 0
end = len(nums)
while beg <= end:
mid = (beg + end) // 2
if mid >= len(nums):
break
curr = nums[mid]
prev = nums[mid - 1] if mid > 0 else curr - 1
forw = nums[mid + 1] if mid < len(nums) - 1 else curr + 1
if curr == target and cmp(prev, forw):
return mid
elif beg == end:
break
elif ncmp(curr):
beg = mid + 1
else:
end = mid
return -1
def searchRange(self, nums: List[int], target: int) -> List[int]:
return [
self.search(nums, target, lambda p, f: p < target, lambda c: c < target),
self.search(nums, target, lambda p, f: f > target, lambda c: c <= target)
]
Top comments (0)