- 二分查找:基于二分查找的算法可以在 O(log n) 的时间复杂度内解决该问题。具体实现方式是,先使用二分查找找到该元素的位置,然后向左和向右扩展,直到找到第一个和最后一个位置。代码如下:
def searchRange(nums, target):
def binarySearch(nums, target, lower):
left, right = 0, len(nums) - 1
ans = len(nums)
while left <= right:
mid = (left + right) // 2
if nums[mid] > target or (lower and nums[mid] >= target):
right = mid - 1
ans = mid
else:
left = mid + 1
return ans
leftIdx = binarySearch(nums, target, True)
rightIdx = binarySearch(nums, target, False) - 1
if leftIdx <= rightIdx and rightIdx < len(nums) and nums[leftIdx] == target and nums[rightIdx] == target:
return [leftIdx, rightIdx]
return [-1, -1]
- 线性扫描:线性扫描的思路是从左到右遍历数组,记录第一次出现目标值的位置,然后继续遍历数组,直到找到最后一次出现目标值的位置,代码如下:
def searchRange(nums, target):
first, last = -1, -1
for i in range(len(nums)):
if nums[i] == target:
if first == -1:
first = i
last = i
return [first, last]
- 使用 Python 内置函数:Python 中有内置函数 bisect_left 和 bisect_right 可以帮助我们实现二分查找。代码如下:
import bisect
def searchRange(nums, target):
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target) - 1
if left <= right and nums[left] == target and nums[right] == target:
return [left, right]
return [-1, -1]
标签:right,target,nums,python,mid,bisect,查找,解法,left
From: https://blog.51cto.com/lzning/9286779