이진 탐색 (Binary Search)

이진 탐색이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.

이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 검색 트리와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 자료구조라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 알고리즘 자체를 지칭한다.

LeetCode 704.Binary Search

정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라.

Solution 1 재귀 풀이

먼저 간단하게 재귀로 이진 검색을 구현할 수 있다. 절반씩 범위를 줄여나가며 맞출 때까지 계속 재귀 호출하면 된다.

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

재귀 제한

파이썬에는 재귀 호출에 대한 호출 횟수 제한이 있으며 기본 값은 1,000으로 설정되어 있다. 이 값은 변경할 수 있으나 일반적으로 코딩 테스트 플랫폼에서는 sys 모듈을 이용한 설정 변경을 허용하지 않기 때문에 가급적 모든 재귀 풀이는 1,000회 반복 이내에 풀이가 가능하도록 구현해야 한다. 파이썬은 재귀 함수 사용 시 이 부분을 고려해야 한다.

Solution 2 반복 풀이

이 문제를 반복 풀이로 변경하면 다음과 같다.

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

Solution 3 이진 검색 모듈

앞선 풀이들에서는 이진 검색을 직접 구현했지만 파이썬에서는 사실 이진 검색을 직접 구현할 필요가 없다. 이진 검색 알고리즘을 지원하는 bisect 모듈을 기본으로 제공하기 때문이다. 여러 가지 예외 처리를 포함한 이진 검색 알고리즘이 깔끔하게 모듈 형태로 구현되어 있으므로, 이 모듈을 이용하면 이진 검색을 파이썬다운 방식으로 다음과 같이 좀 더 간단히 풀이할 수 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index=bisect.bisect_left(nums, target)
        if index<len(nums) and nums[index]==target:
            return index
        else:
            return -1

Solution 4 이진 검색을 사용하지 않는 index 풀이

이전 풀이들은 모두 이진 검색을 통해 풀었지만, 이번에는 이진 검색을 사용하지 않고 한번 시도해본다. 파이썬에서 제공하는, 해당 값의 인덱스를 찾아내는 index() 메소드를 활용하는 방법이다. 이 경우 존재하지 않는 값이라면 에러가 발생하므로 에러인 ValueError를 예외 처리하여 -1을 반환하도록 처리하면 풀이가 가능하다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1

이 방식은 이진 검색이 아니며 이진 검색을 요구하는데 이렇게 풀이해서는 안된다. 오프라인 코딩 테스트에서는 이 같은 방식으로 풀이할 일이 없을 것이고, 온라인 테스트 시에는 시도해볼 만하지만 썩 좋은 방법은 아니다. 경우에 따라서는 페널티를 받을 수도 있으므로 유의해야 한다.

결과적으로 모든 풀이 방식은 속도 차이가 거의 없으며, 재귀 방식이 가장 느린 편이다. 실제로 코딩 테스트 시에는 가급적 재귀나 반복으로 직접 이진 검색을 풀이하는 편이 나중에 코드 리뷰를 하게 되는 경우 더 좋은 평가를 받을 수 있을 것이다.

index()와 bisect는 어떤 차이를 보일까? index()는 앞에서부터 하나씩 확인하며 원하는 값이 나올 때까지 탐색하게 되고, bisect는 원하는 값을 향해 절반씩 범위를 줄여가며 탐색하기 때문에 index()는 비교적 뒤쪽에 있는 수를 찾게 될 경우 실행 속도가 느려지게 되지만 bisect는 거의 일정하다. 그렇기 때문에 배열의 크기가 크고, 찾아야 하는 값이 항상 앞에만 있는 게 아니라면 파이썬의 이진 검색 모듈인 bisect를 적극 활용해야 한다. 참고로, 원래 bisect 모듈은 리스트의 삽입 지점을 찾는 모듈이지만 이처럼 이진 검색으로 위치를 찾는 데에도 매우 유용하게 활용할 수 있다.

LeetCode 33.Search in Rotated Sorted Array

특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를 출력하라.

Solution 1 피벗을 기준으로 한 이진 검색

정렬이 되어 있긴 한데, 피벗을 기준으로 입력값이 돌아간 상황이다. 피벗이 어떤 것인지 모르는 상태이므로, 기존 이진 검색을 그대로 활용할 수는 없고 좀 더 특별한 처리가 필요하다. 먼저 피벗을 찾아야 한다. 이 문제의 예제의 입력값은 [4, 5, 6, 7, 0, 1, 2]이며, 이 경우 피벗은 4이다. 피벗을 찾는 방법은 여러 가지가 있겠지만, 여기서 가장 작은 값을 찾는다면 해당 인덱스가 피벗이 될 수 있다. 다음과 같은 코드로 최솟값을 찾을 수 있다.

left, right=0, len(nums)-1
while left<right:
	mid=left+(right-left)//2
    if nums[mid]>nums[right]:
    	left=mid+1
    else:
    	right=mid

여기서는 이진 검색으로 최솟값을 찾았다. 중앙의 위치를 찾는 코드는 수의 범위를 넘어서지 않도록 left+(right-left)//2로 작성하였다. 더 간단하게 찾는 방법으로는 argmin을 찾는 것이다.
argmin f(x) = {x E S: f(x) = min f(y)}
만약 코딩 테스트가 아니라면 과학 계산 라이브러리인 넘파이 모듈을 활용해 numpy.argmin() 단 한줄로 argmin을 금방 찾을 수 있다. 그러나 여기서는 코딩 테스트인 상황이므로 외부 모듈을 사용할 수 없다. 따라서 다음과 같은 코드로 넘파이의 argmin()을 흉내낼 수 있다.
pivot = nums.index(min(nums))
이 방식이 파이썬답게 한 줄로 처리할 수 있어 훨씬 간단하지만, 여기서는 이진 검색을 직접 구현한다는데 의의가 있으므로, 풀이가 좀 더 길어지더라도 전자를 활용해 계속 구현해본다. 이제 피벗의 위치를 알았으니, 동일한 이진 검색 알고리즘을 적용해 마찬가지로 값을 찾으면 된다.

이번에는 재귀가 아닌 반복으로 풀이해본다.

pivot=left
left, right=0, len(nums)-1
while left<=right:
	mid=left+(right-left)//2
    mid_pivot= ...
    
    if nums[mid_pivot] < target:
    	left=mid+1
    elif nums[mid_pivot] > target:
    	right=mid-1
    else:
    	return mid
    ...

여기서는 앞서 최솟값 left를 찾아내 pivot으로 구성하고, 이를 기준으로 피벗의 위치만큼 살짝 틀어준 mid_pivot을 구성한 다음, 다시 이진 검색을 통해 target 값을 찾았다. 그렇다면 mid_pivot을 실제로는 어떤 식으로 구현하면 될까? 다음 코드를 한번 보자.

mid_pivot = (mid + pivot) % len(nums)

mid_pivot은 중앙의 위치 mid에 피벗 pivot만큼 이동하고, 배열의 길이를 초과할 경우 모듈로 연산으로 회전될 수 있도록 처리했다. 이제 타겟과 값을 비교하는 부분은 mid가 아닌 mid_pivot을 기준으로 하되, left와 right는 mid를 기준으로 이동한다.

값에 대한 비교는 mid_pivot의 위치를 기준으로 하지만, mid의 이동은 기존 이진 검색과 동일하게 left, right를 기준으로 한다. 즉, 다른 포인터를 가리키는 셈이며, 실제로 값에 대한 비교는 pivot의 위치인, 4칸 우측으로 떨어진 mid_pivot을 기준으로 한다. 당연히 최종 결과도 mid_pivot의 값을 반환받아 결과로 삼는다. 전체 코드는 다음과 같다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left, right=0, len(nums)-1
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[right]:
                left=mid+1
            else:
                right=mid
        pivot = left
        left, right=0, len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            mid_pivot=(mid+pivot)%len(nums)
            if nums[mid_pivot]<target:
                left=mid+1
            elif nums[mid_pivot]>target:
                right=mid-1
            else:
                return mid_pivot
        return -1