文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Find First and Last Position of Element in Sorted Array
2. Solution
解析：最容易想到的就是二分查找，只是要进行一些修改，另一个方法是分别从前往后找以及从后往前找，满足条件就退出。
- Version 1
class Solution:
def searchRange(self, nums, target):
length = len(nums)
start = -1
end = -1
left = 0
right = length - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
if mid == 0 or nums[mid - 1] < target:
start = mid
break
right = mid - 1
left = 0
right = length - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
if mid == length - 1 or nums[mid + 1] > target:
end = mid
break
left = mid + 1
return [start, end]
- Version 2
class Solution:
def searchRange(self, nums, target):
length = len(nums)
start = -1
end = -1
for i in range(length):
if nums[i] == target:
start = i
break
if nums[i] > target:
break
if start == -1:
return [start, end]
for i in range(length -1 , -1, -1):
if nums[i] == target:
end = i
break
if nums[i] < target:
break
return [start, end]
