requirements

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

If no target value exists in the array, return [-1, -1].

Advanced:

Can you design and implement an O(log n) algorithm to solve this problem?

Example 1:

Input: nums = [5,7,7,8,8,10] target = 8Copy the code

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6Copy the code

Example 3:

Input: nums = [], target = 0 output: [-1,-1]Copy the code

Tip:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • Nums is a non-decrement array
  • -109 <= target <= 109

The core code

class Solution:
    def searchRange(self, nums: List[int], target: int) - >List[int] :
        lo,hi = 0.len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                break
            elif nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid + 1
        if lo > hi:
            return [-1, -1]
        
        midtarget = mid
        lo,hi = 0,mid
        leftpos = 0
        while lo <= hi:
            if (hi >= 1 and nums[hi - 1] != target) or hi == 0:
                leftpos = hi
                break
            mid = (lo + hi) // 2
            if nums[mid] == target:
                hi = mid
            elif nums[mid] < target:
                lo = mid + 1

        rightpos = 0    
        lo,hi = midtarget,len(nums) - 1
        
        while lo <= hi:
            if (lo <= len(nums) - 2 and nums[lo + 1] != target) or lo == len(nums) - 1:
                rightpos = lo
                break
            mid = (lo + hi + 1) / /2
            if nums[mid] == target:
                lo = mid
            elif nums[mid] > target:
                hi = mid - 1
        
        return [leftpos,rightpos]
Copy the code

Answer: Then we locate a target. We split the data into left and right parts. On the left side we find the left boundary, and on the right side we find the right boundary. Our time is order logn.