이진 검색 추가문제

Question 1: 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.

입력: nums = [5,7,7,8,8,10], target = 8

출력: [3,4]

내 풀이

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

결과

Runtime: 131 ms, faster than 36.36% of Python3 online submissions for Find First and Last Position of Element in Sorted Array. Memory Usage: 15.4 MB, less than 54.70% of Python3 online submissions for Find First and Last Position of Element in Sorted Array.