# 034 Search for a Range

### 34. Search for a Range

https://leetcode.com/problems/search-for-a-range/

• 找左边界：二分，找到一个index
• index对应的值为target
• 并且它左边index-1对应的值不是target（如果index0则不需要判断此条件）
• 如果存在index就将其appendres
• 判断此时res是否为空，如果为空，说明压根不存在target，返回[-1, -1]
• 找右边界：二分，找到一个index（但是此时用于二分循环的l可以保持不变，r重置为len(nums)-1，这样程序可以更快一些）
• index对应的值为target
• 并且它右边index+1对应的值不是target（如果indexlen(nums)-1则不需要判断此条件）
• 如果存在index就将其appendres

AC 代码

class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums : return [-1, -1]

res = []
l, r = 0, len(nums)-1
# search for left bound
while l <= r:
mid = l + ((r - l) >> 2)
if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
res.append(mid)
break
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
if not res:
return [-1, -1]
# search for right bound
r = len(nums)-1
while l <= r:
mid = l + ((r - l) >> 2)
if nums[mid] == target and (mid == len(nums)-1 or nums[mid+1] != target):
res.append(mid)
break
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return res


apachecn/AiLearning