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

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

My Answer 1: Accepted (Runtime: 744 ms - 5.02% / Memory Usage: 15.4 MB - 48.94%)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if target not in nums:
            return [-1, -1]
        
        result = [nums.index(target)]
        
        for _ in range(nums.count(target)-1):
            nums[nums.index(target)] = target-1
            
        result.append(nums.index(target))
        
        return result

python 의 in 을 사용한 방식
맨 처음 target 의 index 를 저장하고
target 의 개수를 나타내는 count(target)-1 만큼 돌려서 값을 바꿔줌 (-1)
그럼 마지막 end 값만 남을테니 그 때의 index 를 저장

List, Tuple 에서의 in 시간 복잡도
= Average: O(n)

Set, Dictionary 에서의 in 시간 복잡도
= Average: O(1), Worst: O(n)

count 시간 복잡도: O(n)

복잡도 계산을 못 하겠네...ㅎ

My Answer 2: Accepted (Runtime: 76 ms - 96.85% / Memory Usage: 15.5 MB - 10.04%)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = -1
        end = -1
        
        for i in range(len(nums)):
            if nums[i] == target:
                start = i
                break
                
        if start == -1:
            return [-1, -1]
        
        for i in range(len(nums)-1, -1, -1):
            if nums[i] == target:
                end = i
                break
        
        return [start, end]

이건 그냥 맨 앞에이랑 맨 뒤에서부터 target 을 찾고 [start, end] 리턴하는 방식

반복문을 사용하면 무조건 O(n) 인 거 같은데.. 어떻게 O(log n) 으로 풀지??

Binary Search

Solution 1: Runtime: 80 ms - 88.97% / Memory Usage: 15.5 MB - 48.94%

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left_idx = self.extreme_insertion_index(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]
    
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def extreme_insertion_index(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1

        return lo

애써 안 보이는 척 하던 Binary Search... 이젠 외워야겠다.
O(logN) 이라고 하네요...

lo, mid, hi 를 이용.