[35번] Search Insert Position

문제 출처 :

 

leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. Binary search

 

이분탐색을 통해 해결 할 수 있다.

 

target이 위치할 수 있는 최소 위치를 찾아야하는 것이고 이분탐색을 통해 어느 인덱스에 위치해야할 지 결정할 수 있다.

이때 사실 이분탐색이 아닌 linear search로도 해결이 가능하다.

 

 

 

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

                if nums[mid] == target:
                    ans = mid
                    break
                if target < nums[mid]:
                    right = mid - 1
                else:
                    ans = left = mid + 1

        return ans

 

 

소스 코드 : 

 

//                                                       This source code Copyright belongs to Crocus

//                                                        If you want to see more? click here >>