[문제풀기] 이진탐색 _ Search Insert Position

이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 알고리즘
중간 값과 찾으려는 값을 비교해서 검색 범위를 절반으로 줄여나간다.
매 단계 검사해야할 요소가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N)이다.

---

문제 : Search Insert Position

 

고유한 정수의 정렬된 배열과 대상 값이 주어졌을 때, 대상이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입되었을 경우의 인덱스를 반환합니다. O(log n) 시간 복잡성이 있는 알고리즘을 작성해야 합니다.

 

예시 1:
입력: 숫자 = [1,3,5,6], 대상 = 5
출력: 2

 

예시 2:
입력: 숫자 = [1,3,5,6], 대상 = 2
출력: 1

 

예시 3:
입력: 숫자 = [1,3,5,6], 대상 = 7
출력: 4

---

나의 풀이

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

        while low <= high:
            mid = low + (high - low) // 2
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return low

sol = Solution()
print(sol.searchInsert([1,3,5,6], 5))

# 결과 : 2