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

MediumLeetCode

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

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

You must write an algorithm with O(log n) runtime complexity.

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]

Example 3:

Input: nums = [], target = 0

Output: [-1,-1]

Constraints

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is sorted in non-decreasing order.
• nums contains only integers.
• target is an integer.

How to solve the problem

1. Not a good solution with T = O(n)

2. Binary Search by splitting leftSearch and rightSearch, but not universal enough

3. Binary Search with the most universal approach

Code

• Approach 1: Linear Search (O(n))

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Not a good solution with T = O(n)
        pre = -1
        suf = -1
        for i, x in enumerate(nums):
            if x == target:
                pre = i
                break

        for i in range(len(nums)-1, -1, -1):
            if nums[i] == target:
                suf = i 
                break

        return [pre, suf]

• Approach 2: Binary Search by splitting leftSearch and rightSearch, but not universal enough

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Binary Search
        # Split leftSearch and rightSearch
        if not nums:
            return [-1,-1]
        
        def leftSearch(nums, target):
            left = 0
            right = len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            if left < len(nums) and nums[left] == target:
                return left 
            else:
                return -1
        
        def rightSearch(nums, target):
            left = 0
            right = len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1

            if right >= 0 and nums[right] == target:
                return right
            else:
                return  -1
    
        pre = leftSearch(nums, target)
        suf = rightSearch(nums, target)

        return [pre, suf]

• Approach 3: Binary Search with the most universal approach

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Binary Search with the most universal approach
        start = lower_bound(nums, target)
        if start >= len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(nums, target + 1) - 1
        return [start, end]

def lower_bound(nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

Complexity

Time complexity: O(log n)

Space complexity: O(1)