34_Find First and Last Position of Element in Sorted Array

[Medium][Tag: array, binary search]

Given an array of integers 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]

Solution: binary search

Idea:

Do two binary search to find the starting position and the ending position.

• starting position

  • if middle position meets the target, the right part of array will be throw away.

• ending position

  • if middle position meets the target, the left part of array will be throw away.

Time Complexity:$O(logn)$

Space Complexity:$O(1)$

def searchRange(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    # find the starting position
    left, right, start = 0, len(nums)-1, -1
    while left <= right:
        middle = left + (right - left)//2
        if nums[middle] == target:
            start = middle
            # throw away the right part of the array
            right = middle - 1
        elif nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    if start == -1:
        return [-1,-1]

    # find the ending position
    left, right, end = start, len(nums)-1, start
    while left <= right:
        middle = left + (right - left)//2
        if nums[middle] == target:
            end = middle
            # throw away the left part of the array
            left = middle + 1
        elif nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return [start, end]