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/?envType=featured-list&envId=top-google-questions

input :

• nums, target

output :

• nums 배열 안에서의 target 값의 시작 idx, 끝 idx 값을 반환하시오.

조건 :

• target이 존재하지 않는다면 [-1, -1]을 반환하시오.

---

Solution explain : Solution1

idea

• 2번의 이분 탐색을 수행하자.

주의

• bisect()와 같은 내장 라이브러리를 사용하는 것도 하나의 방법이다.
• ==을 포함한 부등식을 어떻게 넣을 것인가에 따라 집중하려는 범위가 달라지게 된다.

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

        while l <= r:
            mid = (l + r) // 2
            val = nums[mid]

            if val <= target:
                l = mid + 1
            else:
                r = mid - 1
        temp_l, temp_r = l, r

        l, r = 0, len(nums) - 1

        while l <= r:
            mid = (l + r) // 2
            val = nums[mid]

            if val >= target:
                r = mid - 1
            else:
                l = mid + 1

        if temp_r < l:
            return [-1, -1]
        return [l, temp_r]