[leetcode] 35. Search Insert Position _ python3

35. Search Insert Position

Search Insert Position - LeetCode

 

풀이 코드

정렬된 숫자가 담겨있는 리스트 List와 찾고자 하는 숫자 target이 주어진다. 이때 target이 발견되면 해당 위치의 인덱스를 반환하고, 발견되지 않으면 List에 target이 들어가서 정렬된 경우 target의 인덱스를 반환해 주는 문제이다.

변수 l 에 0을 변수 h에 가장 큰 인덱스 값을 저장한다. 만약, 가장 큰 인덱스(h) 자리에 있는 값 보다 target이 크다면 target은 리스트의 마지막에 들어가기 때문에 h+1을 반환해준다. 그렇지 않다면, binary search 방식으로 탐색한다. (가운데 인덱스를 mid라는 변수에 저장하고, mid 위치의 값과 target을 비교했을 때 mid 위치의 값이 target보다 크거나 같으면 인덱스 h를 mid로 설정한다. 그렇지 않다면 mid값을 1 높인다.)

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

 

시간이 될 때 binary search도 정리하고 문제의 예제도 시각화 해서 추가해 봐야겠다.