Promble
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.
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Input: nums = [], target = 0
Output: [-1,-1]
Approach
- 定义bs函数。
- 分别定义lo，hi = 0, len(nums)
- 首先判断lo < hi， 大于或等于的时候中止函数
- 计算mid ` mid = (lo+hi) // 2`
- 判断边界，并移动。（注意边界问题）
- 计算左边和右边
- hi = bs(target+1)-1 这个就是计算比目标大1的数字的左边界，之后减1就是目标函数的右边界了。
Code
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def bs(x):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
lo = bs(target)
hi = bs(target+1)-1
if lo <= hi:
return [lo, hi]
return [-1, -1]