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

Problem Statement

link: LeetCode.cn LeetCode

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:

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

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

Input: nums = [], target = 0 Output: [-1,-1]

Constraints:

0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums is a non-decreasing array. -10^9 <= target <= 10^9

Solution Approach

The solution uses binary search to efficiently find the first and last positions of the target in the sorted array by locating the lower bound of the target and its next potential position.

Algorithm

1. Binary Search for Efficiency: The solution leverages binary search, ensuring an O(log n) runtime complexity, which is optimal for searching in a sorted array.
2. Lower Bound Technique: It uses the lower bound approach to find the first occurrence of the target and the first occurrence of the next possible value (target + 1) to determine the last occurrence of the target.
3. Edge Case Handling: The algorithm checks if the target is present in the array and returns [-1, -1] if the target is not found, ensuring accurate results even for edge cases like empty arrays or targets outside the range of the array.

Complexity

time complexity: O(log n) n is the number of elements in the array space complexity: O(1) as the solution only uses a constant amount of extra space for variables and does not require additional data structures that grow with the input size.

Implement

    class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(nums: List[int], target: int) -> int:# [left, right]
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return l
            
        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_bound2(nums: List[int], target: int) -> int:#[left, right)
            left = 0
            right = len(nums)
            while left < right:  
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1 
                else:
                    right = mid  
            return left 


        def lower_bound3(nums: List[int], target: int) -> int:
            left, right = -1, len(nums)  #(left, right)
            while left + 1 < right: 
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid 
                else:
                    right = mid 
            return right
        
    

    
    

Twitter  facebook  Email