LeetCode 35. Search Insert Position

Compan

 

 

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

 

풀이

 

 

단순하게 traget 숫자가 배열의 몇번째에 있는지 찾는 문제이다.

 

for문을 통해서 단순하게 해결 할 수 있지만  문제에서 O(log n)의 시간복잡도를 가져야한다는 조건을 가지고 있다.

시간복잡도 O(log n)을 보자마자 이진탐색이 떠올랐고 이진탐색으로 문제를 풀어보았다.

 

왼쪽 시작점과 오른쪽 시작점의 중간을 mid로 지정 한 후 

mid값이 target보다 크다면 right를 mid-1로 지정

mid값이 target보다 작다면 left를 mid+1 로 지정

 

class Solution(object):
    def searchInsert(self, nums, target):
        left =0
        right = len(nums)-1
        while left<right:
            mid = (left+right)//2
            if nums[mid] == target:
                return mid
            elif nums[right] ==target:
                return right
            elif nums[left]== target:
                return left
            if nums[mid]<target:
                right=mid-1
            else:
                left=mid+1

 

하지만.. 계속해서 시간 초과가 났었다. ㅠㅠ 

 

1.무엇이 문젠지 고민을 했는데, 굳이 right left값이 동일한지 확인하는 과정이 불필요하다는걸 깨닫고  mid값으로만 찾게했다 - > 하지만 실패

 

2. if문에서 이미 값이 크다면 right =  mid-1 , 작다면  left =mid+1로 값을 변경되도록 만들었는데 부호를 반대로 줘서 계속해서 돌다 mid가 0으로 나누어떨어지며 시간초과가 난다는걸 발견 한 후 다시 수정했다.

 

class Solution(object):
    def searchInsert(self, nums, target):
        left =0
        right = len(nums)-1

        while left<=right:
            mid = (left+right)//2
            m = nums[mid]
            if nums[mid]== target:
                return mid
            if nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return left

 

해결 완료