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

Example 2:

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

Output: [-1,-1]

## Solution

from typing import List

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
lo = 0
hi = len(nums) - 1
ret = [-1, -1]

if not nums: return ret

while lo < hi:
mid = lo + (hi-lo) // 2

if nums[mid] < target:
lo = mid + 1
else:
hi = mid

if nums[lo] == target:
ret[0] = lo
else:
return ret

hi = len(nums) - 1
while lo < hi:
mid = lo + (hi-lo) // 2 + 1

if nums[mid] > target:
hi = mid - 1
else:
lo = mid

ret[1] = hi
return ret


## Test Cases

test = Solution()
assert test.searchRange([5,7,7,8,8,10], 8) == [3,4]
assert test.searchRange([5,7,7,8,8,10], 6) == [-1,-1]
assert test.searchRange([5,7,7,8,8,10], 5) == [0,0]
assert test.searchRange([5,7,7,8,8,10], 10) == [5,5]
assert test.searchRange([5,5,5,5,5,7,7,8,8,10], 5) == [0,4]
assert test.searchRange([5,5,5,5,5,7,7,8,8,10],7) == [5,6]
assert test.searchRange([],0) == [-1,-1]
assert test.searchRange([1],0) == [-1,-1]
assert test.searchRange([1],1) == [0,0]
assert test.searchRange([1,1],1) == [0,1]
print('All Passed!')


## Big O Analysis

Space Complexity: O(1)

Time Complexity: O(log(N))