在Python中的排序数组中查找元素的第一个和最后一个位置
假设我们有一个整数数组A。它按升序排序，我们必须找到给定目标值的开始和结束位置。当在数组中找不到目标时，返回[-1，-1]。因此，如果数组类似于[2,2,2,3,4,4,4,4,5,5,6]，而目标为4，则输出将为[4,7]
为了解决这个问题，我们将遵循以下步骤-
最初res：= [-1，-1]，设置low：= 0，high：=数组A的长度
从低到高
高：=中，res [0]：=中，res [1]：=中
中：=低+（高–低）/ 2
如果A [mid]是目标，则
否则，当A [mid] <目标时，则低：=中+ 1，否则高：=中
如果res [0] = -1，则返回res
低：= res [0] + 1，高：=长度
从低到高
低：=中+ 1，res [1]：=中
中：=低+（高–低）/ 2
如果A [mid]是目标，则
否则，当A [mid] <目标时，则低：=中+ 1，否则高：=中
返回资源
示例(Python)
让我们看下面的实现以更好地理解-
class Solution(object):def searchRange(self, nums, target):
res = [-1,-1]
low = 0
high = len(nums)
while low<high:
mid = int(low + (high-low)//2)
if nums[mid] == target:
high = mid
res[0]=mid
res[1]=mid
elif nums[mid]<target:
low = mid+1
else:
high = mid
if res[0] == -1:
return res
low = res[0]+1
high = len(nums)
while low<high:
mid = int(low + (high-low)//2)
if nums[mid] == target:
low = mid+1
res[1] = mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid
return res
ob1 = Solution()print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))
输入值
[2,2,2,3,4,4,4,4,5,5,6]4
输出结果
[5, 8]
以上是 在Python中的排序数组中查找元素的第一个和最后一个位置 的全部内容， 来源链接： utcz.com/z/359942.html
