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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

정렬된 리스트 nums에서 target이 있을떄 첫번째와 마지막 인덱스를 반환하는 문제이다.

에를 들어 nums = [5,7,7,8,8,10]가 있고 target이 8일때
3,4를 반환해야한다.

해당 테.케의 경우에는 일반적인 binary search를 이용하여 풀어도 정답이 나오는 문제이다.

그런데 만약 nums가 [5,7,7,8,8,8] 이라면 index 4의 8이 아닌 3,5를 반환해야한다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.searchtarget(nums, target, True)
        right = self.searchtarget(nums, target, False)
        return [left, right]

    def searchtarget(self, nums, target,leftBias ):  
        l , r = 0, len(nums)-1
        i = -1
        while l <=r:
            mid = (l+r) // 2
            if target > nums[mid]:
                l = mid+1
            elif target < nums[mid]:
                r = mid -1 
            else:
                i = mid
                if leftBias:
                    r = mid -1
                else:
                    l = mid +1
        return i

22.02.18 복습

비슷하지만 다른 풀이
left 구하는 함수, right 구하는 함수 나누어서 풀었다

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def helperLeft(nums,target):
            l,r = 0, len(nums)-1
            while l <=r : 
                m = (l+r) // 2
                if nums[m] < target:
                    l = m + 1
                else : 
                    r = m -1
            return l

        def helperRight(nums,target):
            l,r = 0, len(nums)-1
            while l<=r:
                m = (l+r)//2
                if nums[m] <= target: 
                    l = m +1
                else :
                    r = m -1
            return r 

        left = helperLeft(nums,target)
        right = helperRight(nums,target)
        if left <= right:
            return [left,right]
        return [-1,-1]