algoadvance

You are given an array of integers nums sorted in non-decreasing order, and an integer target. Your task is to find the starting and ending position of a given target value in the array.

Return an array of length 2, where the first element is the starting position and the second element is the ending position of target. If target is not found in the array, return [-1, -1].

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

Clarifying Questions

  1. Q: Can the array contain duplicate elements?
    • A: Yes, the array can contain duplicates.
  2. Q: What should be returned if the target is not found in the array?
    • A: Return [-1, -1].
  3. Q: Should I handle any special cases, like an empty array?
    • A: Yes, if the array is empty, return [-1, -1].

Strategy

To achieve the required O(log n) time complexity, we can use a binary search approach. Here’s the plan:

  1. Find the First Position of target:
    • Use binary search to locate the first occurrence of target.
    • Initialize left to 0 and right to the length of the array minus one.
    • Narrow down the search space by comparing the midpoint value to the target. If the midpoint value is greater than or equal to target, eliminate the right half; otherwise, eliminate the left half.
    • When a match is found, continue searching in the left half to find the leftmost occurrence.
  2. Find the Last Position of target:
    • Use a similar binary search approach to locate the last occurrence of target.
    • Again, initialize left to 0 and right to the length of the array minus one.
    • Narrow down the search space using the same comparison logic. If the midpoint value is less than or equal to target, eliminate the left half; otherwise, eliminate the right half.
    • When a match is found, continue searching in the right half to find the rightmost occurrence.
  3. Combine Results:
    • Return the indices found from the two binary searches. If the target is not present, both searches will return -1.

Code

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

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

    first_pos = findFirst(nums, target)
    last_pos = findLast(nums, target)

    return [first_pos, last_pos]

# Example Usage
nums = [5,7,7,8,8,10]
target = 8
print(searchRange(nums, target))  # Output: [3, 4]

Time Complexity

Try our interview co-pilot at AlgoAdvance.com