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

문제

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.

오름차순으로 정렬된 배열 nums에 대해 특정 target 숫자의 범위를 리스트로 리턴하시오.
숫자가 없을시 [-1, -1] 을 리턴하면 됩니다.

예시

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

제한

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

풀이

특정 값의 왼쪽 끝을 찾는 binary search와 오른쪽 끝을 찾는 binary search를 두번 사용해 풀었다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 찾지 못하면 [-1, -1] 리턴됨.
        left = right = -1
        start = 0
        end = len(nums)-1
        # 값의 왼쪽 끝 위치를 찾기 위한 Binary search
        while start <= end:
            mid = (start + end) // 2
            if (nums[mid] == target) and ((mid > 0 and nums[mid-1] != target) or (mid == 0)):
                left = mid
                break
            elif nums[mid] >= target:
                end = mid - 1
            else:
                start = mid + 1
        start = 0
        end = len(nums)-1
        # 값의 오른쪽 끝을 찾기 위한 Binary search
        while start <= end:
            mid = (start + end) // 2
            if (nums[mid] == target) and ((mid < len(nums)-1 and nums[mid+1] != target) or (mid == len(nums)-1)):
                right = mid
                break
            elif nums[mid] <= target:
                start = mid + 1
            else:
                end = mid - 1
        return [left, right]
        

O(logN) 의 시간복잡도를 가지는 binary search가 두번 사용되어 시간복잡도는 O(logN) 이다.