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

Description

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:

• nums is a non-decreasing array

Approach：

When we come across a search problemin a sorted array and it comes with the constraint that we need to solve it efficiently in O(log n) time, the first thing that should pop into our heads is binary search.

Now, this particular problem is like a twist on binary search. It asks us to keep searching within the array until we find the start and the end position of the target number we're looking for.

To make that happen, we apply a binary search, but instead of immediately giving back the index where we spot the number, we store the number temporarily and keep on searching for the next number until the sequence ends.

Codes

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = [-1, -1]
 
        def binary_search(is_start):
            index = -1
            left = 0
            right = len(nums) - 1
 
            while (left <= right):
                mid = left + (right - left) // 2
                num = nums[mid]
                if num == target:
                    # store the temporary index in index then keep searching
                    index = mid
                    if is_start:
                        # search the left half if searching for the starting of the sequesce
                        right = mid - 1
                    else:
                        # search the right half if searching the end of the sequence
                        left = mid + 1
                elif num > target:
                    right = mid - 1
                else:
                    left = mid + 1
 
            return index
 
        result = [searchTarget(True), searchTarget(False)]
 
        return result

Complexity

• Time Complexity: ;
  It is a binary search, so we cut have the size after each search, so the time complexity will be O(log n)
• Space Complexity: