目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

二、解题思路

利用二分法找左区间和右区间，左区间一旦大于等于则r=mid，右区间一旦小于等于则l=mid。有点绕但其实是找区间的问题，差点没绕过来，哎。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def searchRange(self, nums: list, target: int) -> list:
     
    
   

    

     

    
    

     

       res = [-1, -1]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       l, r = 0, len(nums) - 1
     
    
   

    

     

    
    

     
 while l < r:
     
    
   

    

     

    
    

     

       mid = l + (r - l) // 2  # 向左取整
     
    
   

    

     

    
    

     
 if nums[mid] < target:  # 首先考虑一定不存在解的区间，则有+1（或者-1）
     
    
   

    

     

    
    

     

       l = mid + 1
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       r = mid
     
    
   

    

     

    
    

     
 if not nums or nums[l] != target:  # 用例中有nums = [] 的情况
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     

       res[0] = l
     
    
   

    

     

    
    

     
 # l=r=mid
     
    
   

    

     

    
    

     

       l, r = r, len(nums) - 1
     
    
   

    

     

    
    

     
 while l < r:
     
    
   

    

     

    
    

     

       mid = l + (r - l + 1) // 2  # 向右取整
     
    
   

    

     

    
    

     
 if nums[mid] > target:
     
    
   

    

     

    
    

     

       r = mid - 1
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       l = mid
     
    
   

    

     

    
    

     

       res[1] = r
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums = [5, 7, 7, 8, 8, 10]
     
    
   

    

     

    
    

     

       target = 8
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.searchRange(nums, target)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110475417