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

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
回到顶部