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.

'''
[1] linear search)

idea::
1. find target value from left to right
2-1. if there is no target value in list, return [-1,-1]
2-2. if there is, find target value from right to left
3. return range

code::
def searchRange(self, nums: List[int], target: int) -> List[int]:
    indices=[-1,-1]

    for left in range(len(nums)):
        if nums[left]==target:
            indices[0]=left
            break
    else: # break checker
        return indices

    for right in range(len(nums)-1,-1,-1):
        if nums[right]==target:
            indices[1]=right
            break

    return indices
    
-T/C: O(2n)
-S/C: O(2)==O(1)
'''

'''
[2] binary search + optimization)

idea::
1. find left index of target val using binary search
2. find right index of target val using binary search. if find left, we can use this point(optimization)

code::
(below)

-T/C: O(2logn)==O(logn)
-S/C: O(2)==O(1)
'''

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        indices=[-1,-1]
        
        # find left index
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid
                
        # when there is no target value
        if not nums or nums[left]!=target:
            return indices
        
        
        indices[0]=left
        
        # init right & find right index
        right=len(nums)-1
        while left<right:
            mid=(left+right)//2+1
            if nums[mid]>target:
                right=mid-1
            else:
                left=mid
        indices[1]=left
                
        return indices