動機
lowerbound與upperbound只差一個等號!!
Problem
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]
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]
Example 3:
Input: nums = [], target = 0Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
Sol
class Solution:
def searchRange(self, ns: List[int], val: int) -> List[int]:
def lower(n):
a,b = 0,len(ns)
while a<b:
mid = (a+b)//2
if ns[mid] >= n:
b = mid
else:
a = mid+1
return a
def wierd_upper(n):
a,b = 0,len(ns)
while a<b:
mid = (a+b)//2
if ns[mid] > n:
b = mid
else:
a = mid+1
return a-1
a,b = lower(val),wierd_upper(val)
a,b = (a if 0 <= a < len(ns) and ns[a] == val else -1), (b if 0 <= b < len(ns) and ns[b] == val else -1)
return [a,b]