首页 > itarticle > 34. search for a range

34. search for a range

admin 11月 13, 2020 0

题目

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

题意

二分法解决

Python实现

class (object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        begin,end=0,len(nums)-1
        tb,te=0,0
        while begin<=end:
            mid=begin+int((end-begin)/2)
            if target>nums[mid]:
                begin=mid+1
            elif target<nums[mid]:
                end=mid-1
            else:
                i=mid
                while i>=0 and nums[i]==nums[mid] :i-=1
                tb=i+1
                i=mid
                while i<len(nums) and nums[i]==nums[mid] :i+=1
                te=i-1
                return [tb,te]
        return [-1,-1]