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

Problem: 

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.

 

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]
 

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

위 문제는 주어진 nums list에 중복된 숫자가 있다면, 그 수의 시작점과 끝점을 찾는 문제다. 시간복잡도는 O(log(n))으로 이루어져야 한다. 

발상:

이 문제의 시간복잡도가 O(log(n))인 것을 보고, Binary Search를 떠올렸다. Binary Search밖에 아는게 없기 때문이다. 하하

 

코드 짜기:

코드는 내가 직접 100% 짜지 못했다. 그래서 다른 사람들 Solution을 참고했다. 형식은 이렇다. 

기존의 Binary Search를 유지하고, left를 탐색할 건지 right를 탐색할건지 조건만 추가해 주는 거였다. left를 탐색하면 start값이 나오고, right를 탐색하면 end값이 나온다. 

 

코드:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findBound(nums: List[int],target:int, isleft:bool) -> int:
            left,right = 0, len(nums)-1 
            mid = 0 
            boundary = -1
            while left <= right:
                mid = (left + right) // 2 
                if target < nums[mid]:
                    right = mid - 1 
                elif target > nums[mid]:
                    left = mid + 1 
                else:
                    boundary = mid 
                    if isleft:
                        right = mid - 1 
                    else:
                        left = mid + 1 
            return boundary 
        left = findBound(nums,target,True)
        if left == -1:
            return [-1,-1]
        right = findBound(nums,target,False)
        return [left,right]

 

 

내가 본 Solution1:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        first, last = -1, -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                first = mid
                last = mid
                while first > 0 and nums[first - 1] == target:
                    first -= 1
                while last < len(nums) - 1 and nums[last + 1] == target:
                    last += 1
                return [first, last]
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return [first, last]

 

내가 본 Solution2:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findFirst(nums, target):
            left, right = 0, len(nums) - 1
            first = -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    first = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return first
        
        def findLast(nums, target):
            left, right = 0, len(nums) - 1
            last = -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    last = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return last
        
        first = findFirst(nums, target)
        last = findLast(nums, target)
        return [first, last]