[리트코드 LeetCode] Search for a Range (Find First and Last Position of Element in Sorted Array) (Python)

Search for a Range (Find First and Last Position of Element in Sorted Array) 

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/

Explore - LeetCode

• 분류: Top Interview Questions - Medium - Sorting and Searching

문제

• 주어진 정수 배열 nums는 non-decreasing order로 정렬되어 있다. 주어진 target value의 시작/끝 위치를 찾아라.
• 만약 target이 배열에 없다면 [-1, -1]을 반환하라.
• O(log n) 시간 복잡도를 가진 알고리즘으로 해결하라.
• type nums: List[int] / type target: int / rtype: List[int]

예시

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]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

조건

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

풀이

1. 이분 탐색 + 선형 탐색

빈 배열이면 바로 [-1, -1] 반환

이미 정렬된 배열이므로 이분 탐색으로 특정 수를 찾을 수 있음

특정 수를 찾은 다음에 while로 start/end 찾기 (선형 탐색)

class Solution(object):
    def searchRange(self, nums, target):
        if nums == []:
            return [-1, -1]
        l, r = 0, len(nums)-1
        start, end = -1, -1
        while l <= r:
            mid = (l+r) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                start = end = mid
                break
        while (start-1) >= 0 and nums[start-1] == target:
            start -= 1
        while (end+1) < len(nums) and nums[end+1] == target:
            end += 1
        return [start, end]

Time: O(n) / Space: O(1)

Runtime: 71 ms (beats 9.78%) / Memory Usage: 14.3 MB (beats 99.94%)

 

2. 이분 탐색 2번

• https://velog.io/@j1min/Python-이분탐색-라이브러리-bisect-직접구현

이분 탐색은 해당 원소가 들어갈 가장 왼쪽 자리를 반환하는 것과 가장 오른쪽 자리를 반환하는 것 2가지로 나눌 수 있다.

이 2가지 함수를 직접 구현하거나, left를 구현한 후 right는 target을 target+1로 하여 구하는 방법이 있다.

값을 비교하는 if문에서 nums[mid] < target으로 하느냐 nums[mid] > target으로 하느냐에 따라 반환하는 값이 달라진다. nums[mid] == target의 경우는 else에 들어간다.

 

(1) bisect 라이브러리의 left, right 함수를 이용하는 방법

class Solution(object):
    def searchRange(self, nums, target):
        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target)-1
        if left <= right:
            return [left, right]
        else:
            return [-1, -1]

Time: O(log n) / Space: O(1)

Runtime: 59 ms (beats 79.62%) / Memory Usage: 14.6 MB (beats 40.94%)

 

(2) left 함수를 구현한 후 left(target+1)-1로 right를 구하는 방법

class Solution(object):
    def searchRange(self, nums, target):
        def search(x):
            lo, hi = 0, len(nums)           
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid+1
                else:
                    hi = mid                    
            return lo
        
        lo = search(target)
        hi = search(target+1)-1
        
        if lo <= hi:
            return [lo, hi]
                
        return [-1, -1]

Runtime: 66 ms (beats 33.71%) / Memory Usage: 14.6 MB (beats 40.94%)