Binary Search | 알고달레

LeetCode의 704번째 문제인 Binary Search 문제를 함께 풀어보도록 하겠습니다.

문제

오름차순으로 정렬된 정수 배열 nums과 정수 target이 주어졌을 때 nums에서 target을 찾는 함수를 작성하시오. 만약 target이 존재한다면 해당 인덱스를 반환하고, 존재하지 않으면 -1을 반환해야 합니다.

O(log n)의 실행 시간 복잡도를 가진 알고리즘으로 작성해야 합니다.

예제

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

풀이 1: 재귀

이 문제는 제목 그대로 이분 탐색(Binary Search) 문제인데요. 입력 배일이 이미 정렬되어 있으니 별도의 사전 작업이 없이 바로 이분 탐색을 적용할 수 있을 것 같아요.

이분 탐색은 재귀 알고리즘으로 구현할 수 있고 반복 알고리즘으로도 구현할 수 있는데요. 먼저 재귀 알고리즘으로 구현해보겠습니다.

기본 아이디어는 검색 범위의 중앙에 있는 값과 찾으려는 값을 비교한 결과에 따라서 검색 범위를 계속적으로 절반씩 줄여나가는 것입니다.

만약 중앙에 있는 값보다 찾으려는 값이 크다면? 오른편 절반으로 검색 범위를 줄이기 위해서 재귀 함수의 첫 번째 인자로 mid + 1을 넘겨 호출을 합니다.
만약 중앙에 있는 값보다 찾으려는 값이 작다면? 왼편 절반으로 검색 범위를 줄이기 위해서 재귀 함수의 두 번째 인자로 mid - 1을 넘겨 호출을 합니다.
만약 중앙에 있는 값이 찾으려는 값과 같다면? 찾으려는 값을 찾았으므로 중앙 인덱스(mid)를 반환합니다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def dfs(low, high):
            if low > high:
                return -1
            mid = (low + high) // 2
            if nums[mid] < target:
                return dfs(mid + 1, high)
            elif nums[mid] > target:
                return dfs(low, mid - 1)
            else:
                return mid
        return dfs(0, len(nums) - 1)

이 풀이의 시간 복잡도는 함수를 호출할 때 마다 검색 범위가 절반으로 줄어들므로 O(log n)이 됩니다. 공간 복잡도는 호출 스택의 깊이가 최대 log n이 되므로 공간 복잡도도 동일한 O(log n) 입니다.

풀이 2: 반복

이분 탐색은 반복 알고리즘을 사용해서도 어렵지 않게 구현할 수 있는데요. 검색 범위의 시작 지점과 종료 지점을 변수에 저장해놓고 중앙에 있는 값과 찾으려는 값을 비교한 결과에 따라 시작 지점 또는 종료 지점을 적절히 갱신해주면 됩니다.

만약 중앙에 있는 값보다 찾으려는 값이 크다면? low 값을 mid + 1로 변경하여 왼쪽 반쪽을 버립니다.
만약 중앙에 있는 값보다 찾으려는 값이 작다면? high 값을 mid - 1로 변경하여 오른쪽 반쪽을 버립니다.
만약 중앙에 있는 값이 찾으려는 값과 같다면? mid 값을 반환합니다.

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

이 풀이는 반복문이 매 단계에서 검색 범위가 절반으로 줄어들므로 시간 복잡도가 O(log n)이 됩니다. 공간 복잡도 동일한 변수(low, high, mid)를 계속해서 재활용하여 배열에 크기에 영향을 받지않고 O(1)이 입니다.

마치면서

코딩 시험에서 이분 탐색(Binary Search)을 다루는 유형의 문제에서는 이 문제가 가장 기본이 된다고 볼 수 있는데요. 이 문제가 너무 쉬우셨다면 비슷하지만 좀 더 어려운 문제인 Find Minimum in Rotated Sorted Array도 풀어보시라고 추천드립니다. 이분 탐색 알고리즘에 대해서는 별도 포스팅에서 자세히 다루었으니 참고해보시면 도움이 될 것 같습니다.