Skip to content

034 Search for a Range

34. Search for a Range

题目:

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

难度 : Medium

思路:

二分法,先找target出现的左边界,判断是否有target后再判断右边界

  • 找左边界:二分,找到一个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


回到顶部