[99클럽 코테 스터디] 11일차 TIL - 이분탐색, Search Insert Position

[11일차] 이분탐색

문제: https://leetcode.com/problems/search-insert-position/description/

* 대충 번역: 중복되지 않는 정수와 target 값이 포함된 정렬된 배열이 주어질 때, target의 인덱스를 반환하라. target이 없다면, 들어가야 하는 순서의 인덱스를 반환하라. O(logn)의 시간복잡도로, 0초대에 해결되는 알고리즘이어야 한다.

Solution

빠른 탐색을 위해서는 이분탐색 알고리즘을 활용할 수 있다.

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start = 0
        end = len(nums) - 1

        while start <= end:
            mid = (start + end) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1

        return start

while 반복문을 빠져나왔다면, end < start 가 되었다는 뜻이다. 즉 반복문을 빠져나오기 직전, nums[mid] < target < nums[start] 인 상황이 된 것이다. 그러므로 target은 start 위치에 들어가야 한다.

나다어

• 이분탐색에서, mid값이 곧 검사 위치이므로 인덱스를 end = mid - 1, start = mid + 1 로 업데이트해 주어야 한다. 이미 검사한 mid는 제외하는 것이다.
• 파이썬에서 / 는 나눗셈 결과, // 는 몫의 결과이다.