在排序数组中查找元素的第一个和最后一个位置
时间: 2023-12-06 07:05:29 浏览: 139
你可以使用二分查找算法来解决这个问题。首先,通过二分查找找到目标元素的任意一个位置。然后,向左右两边扩展,分别找到第一个和最后一个等于目标元素的位置。
下面是一个示例的实现代码(假设数组已经按升序排序):
```python
def searchRange(nums, target):
# 二分查找找到任意一个目标元素位置
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
break
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
else:
# 没有找到目标元素
return [-1, -1]
# 向左扩展找到第一个目标元素位置
i = mid
while i > 0 and nums[i-1] == target:
i -= 1
# 向右扩展找到最后一个目标元素位置
j = mid
while j < len(nums)-1 and nums[j+1] == target:
j += 1
return [i, j]
```
你可以调用这个函数,并传入排序好的数组和目标元素来查找第一个和最后一个位置。如果找到了目标元素,函数会返回一个包含两个位置的列表,如果没有找到,则返回 [-1, -1]。
阅读全文