博客

• 题号：
  
  力扣34
  
• 知识点：二分查找
• 目标完成度：33/150
• 总结
  
  题干：
  
  

思路：

• 1.总体思路：首先用二分查找最左边的
  
target

  ，然后再用二分查找最右边的
  
target

• 2.具体操作：查找最左边的
  
targe

  t时，让右边的指针不断收缩，当
  
nums[mid] < target

  时，说明
  
mid

  左边的元素都严格小于
  
target

  ，因此让
  
left = mid + 1

  ，后面再判断
  
if nums[left] == target:

  ，如果不相等就说明没有查找到，返回
  
-1

• 3.同理，查找最右边的
  
targe

  时，让左边的指针不断收缩，但是要注意，当
  
left = mid

  时，在求解中间位置时要加一，
  
mid = (right + left + 1) // 2


class Solution:
    def searchRange(self, nums:list, target:int) -> list:
        def searchLeft(nums, target):
            left = 0
            right = len(nums)- 1
            while left < right:
                mid = (right + left) // 2
                if nums[mid] == target:
                    right = mid
                if nums[mid] < target:
                    left = mid + 1
                if nums[mid] > target:
                    right = mid
            if nums[left] == target:
                return left
            else:
                return -1
        
        def searchRight(nums, target):
            left = 0
            right = len(nums) - 1
            while left < right:
                mid = (right + left + 1) // 2
                if nums[mid] == target:
                    left = mid
                if nums[mid] < target:
                    left = mid
                if nums[mid] > target:
                    right = mid -1
            if nums[right] == target:
                return right
            else:
                return -1
        if len(nums) == 0:
            return [-1, -1]
        left = searchLeft(nums, target)
        right = searchRight(nums, target)
        return [left, right]