测试人社区

34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums 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] .

自己写的答案:

class Solution:        
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 判断列表长度
        if len(nums) == 0:
            return [-1, -1]
        elif len(nums) == 1:
            return [0, 0] if nums[0] == target else [-1, -1]
        else:
            low = self.search_first(nums, target)
            high = self.search_last(nums, target)
            return [low, high]
        
    def search_first(self, nums: List[int], target: int):
        low = 0
        high = len(nums) - 1
        
        while low <= high:
            mid = low + (high - low >> 1)
            if nums[mid] >= target:
                high = mid - 1
            else:
                low = mid + 1 
        if low <len(nums) and nums[low] == target:
            return low
        else:
            return -1
        
    def search_last(self, nums: List[int], target: int):
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = low + (high - low >> 1)
            if nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1 
        if high <len(nums) and nums[high] == target:
            return high
        else:
            return -1

其实查找最后一个和查找第一个是可以合并成一个函数的,然后通过一个标志位来判断是找第一个还是最后一个,然后确定来更新low还是更新high,这里我就不写了