[LeetCode] 34 | Find First and Last Position of Element in Sorted Array | Python

---

문제 링크: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

---

문제

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.

---

조건

• $0$ <= nums.length <= $10^5$
• $-10^9$ <= nums[i] <= $10^9$
• nums is a non-decreasing array.
• $-10^9$ <= target <= $10^9$

---

내 풀이

단순하게 생각하면 nums가 sorted array이기 때문에 앞이나 뒤에서부터 차례로 찾으면 된다.

하지만 그렇게하면 문제에서 정의한 O(log n)인 방법이 아니다.

정렬된 리스트에서 찾는 시간을 줄이는 방법은 Binary Search(이분탐색)이 적절하다.

 

먼저 target이 nums에 존재하지 않는다면 [-1, -1]을 리턴한다.

그 후에 BS를 이용해서 target의 위치를 찾은 후, 그 앞 뒤로 target이 시작하는 지점과 끝나는 지점을 찾는다.

---

코드

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if target not in nums:
            return [-1, -1]
        
        left, right = 0, len(nums)
        
        while left < right:
            mid = (left+right)//2
            
            if nums[mid] == target:
                break
                
            elif nums[mid] < target:
                left = mid
            
            elif target < nums[mid]:
                right = mid
         
        for n in range(mid, -1, -1):
            if nums[n] < target:
                n += 1
                break
        start = n
        
        for n in range(mid, len(nums)):
            if nums[n] > target:
                n -= 1
                break
        end = n
        
        return [start, end]