menu

[LeetCode] 034. Find First and Last Position of Element in Sorted Array *

Problem (Medium)

034. 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].

Example 1:

  • Input: nums = [5,7,7,8,8,10], target = 8
  • Output: [3,4]

Example 2:

  • Input: nums = [5,7,7,8,8,10], target = 6
  • Output: [-1,-1]

Idea

See the explanation of Approach 2. LeetCode Solution

Solution

class Solution1:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not len(nums):
            return [-1, -1]
        low, high = 0, len(nums)-1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] >= target:
                high = mid
            else:
                low = mid + 1

        res_left = low
        if nums[res_left] != target:
            return [-1, -1]
        else:
            low, high = 0, len(nums)-1
            while low < high:
                mid = (low + high) // 2
                if nums[mid] > target:
                    high = mid
                else:
                    low = mid + 1
            if nums[low] == target:
                res_right = low
            else:
                res_right = low - 1
            return [res_left, res_right]

Complexity

  • Time: $O(\log n)$
  • Space: $O(1)$



KF

Comments