📌 이진탐색 (Binary Search)

이진탐색

데이터셋이 있고, 그 안에서 원하는 값(target)을 찾고자 할 때는, 보통 데이터셋 제일 앞 데이터부터 순차적으로 검색을 한다. 그러나 이 방식은 운이 나쁘면 target을 찾는데 아주 오랜 시간이 걸릴 수 있다.

엑셀을 많이 이용해본 유저는 알겠지만, VLOOKUP 함수에 “정확히 일치” 옵션을 주고 사용하면, 범위에서 target을 순서대로 검사해가며 찾게 되는데, 엑셀 계산 속도가 체감이 될 정도로 느려진 경험을 해본 적이 한번쯤은 있을 것이다. 순차검색의 문제다.

하지만 데이터셋이 오름차순으로 정렬이 되어있다면, 특별한 알고리즘으로 원하는 데이터를 빠르게 찾을 수 있다. 이진탐색 알고리즘인데, 나무위키에 있는 그림만 봐도 어떤 알고리즘인지 쉽게 알 수 있을 것이다.

​마치 사전에서 어떤 단어를 찾을 때, 적당히 사전을 펴서 만일 그 단어보다 앞에 있는 단어라면 그 위치부터 뒤쪽으로 다시 적당한 위치를 어림잡아 펴보고하는 것과 같을 것이다.

그래서 왜 데이터셋이 사전에 오름차순으로 정렬이 되어있어야 하는지도 충분히 이해가 될 것이라 생각한다.

코드구현

찾고자 하는 값을 target, 데이터셋을 A라고 한다면, 대체로 아래와 같은 방식으로 찾을 수 있다.

• 전체 A 범위에서 중간위치값 middle을 찾아서, target과 비교
• middle < target이면 middle 포함 그 아래 데이터들을 모두 버리고, middle > target이면 middle 포함 그 위 데이터들을 모두 버림
• 버리지않고 남은 데이터들을 다시 A로 정의하고, 위 단계를 middle == target이 될 때까지 계속 반복

알고리즘 이해는 간단하지만, 이를 실제 코드로 구현하려하면 생각보다 까다롭다. 여기저기 찾아봐서 개인적으로 가장 잘 구현되었다라고 느끼는 코드를 가져와서 아래 코딩테스트 문제에 적용해보았다.

leetcode: 35. Search Insert Position

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

오름차순으로 주어진 데이터셋이 있을 때, 어떤 특정 값(target)이 위치한 인덱스를 찾거나, target이 없다면 오름차순을 위반하지 않고 삽입이 가능한 인덱스를 찾아 리턴하는 문제다.

위 문제는 target을 찾거나, 아니면 찾지 못했을 때 target이 들어갈 위치를 찾거나와 같이 두가지 케이스를 나눠서 해결해야하는 것처럼 보이는데 그렇게 문제를 풀 필요는 없다.

위 이진탐색 알고리즘을 계속 반복하다가 끝까지 target을 찾지 못해도, 마지막 반복까지 탐색한 그 자리가 target이 들어갈 인덱스가 되도록 짤 수 있다. 아래 코드는 그렇게 되도록 만들어져있는데, 누가 처음 고안했는지 참 대단하다고 느꼈다.

# python
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums)

        while i < j:
            m = i + (j-i) // 2
            if nums[m] < target:
                i = m + 1
            else:
                j = m

        return i

위에서 i와 j는 데이터셋에 해당하는 nums의 버려지지않은 채 아직 남아있는 데이터들의 인덱스를 가리키는 값으로, i이상 j미만으로 정의하였다. 알고리즘 풀이에서 종종 볼 수 있는 two pointers이지만, j가 “미만”으로 정의되어 있다는 점에 주의해야 한다.

m은 중간 인덱스를 구하고 있고, 중간값인 nums[m]과 target을 비교, 불필요한 데이터들을 버리는 것을 i와 j의 값을 조정하는 것으로 대신하고 있다. 참고로 i이상 j미만으로 정의했기 때문에 값조정 수식이 서로 다르다.

​위 코드가 훌륭한 점은, 어떠한 케이스에서도 반복을 계속하다보면 반드시 i == j가 되는 시점이 발생하며, 이때의 i 또는 j 값이 target이 오름차순을 유지한 채 삽입 가능한 인덱스가 된다는 점이다.

또한 반복문 중간에 target을 찾았더라도 그 인덱스를 리턴하지 않고 계속 반복을 진행하도록 되어있는데, 만일 아래와 같이 동일값이 여러개 있는 데이터셋 케이스에도 작동이 되어야 하기 때문이다.

target = 7
nums = [2, 3, 5, 7, 7, 7, 7, 7, 7, 11, 13]

코드를 보면, nums[m] == target인 경우 j를 조정하도록 되어있다. 즉 m 인덱스보다 뒤에 있는 데이터들을 버리는 셈이 되며, 바로 위 케이스 에서는 반복문 종료가 되었을 때 i 또는 j는 7 데이터들이 모여있는 구간의 제일 앞 인덱스인 3 이 된다. 만일 i를 조정하도록 했다면 결과는 7 데이터들이 모여있는 구간의 제일 뒤쪽의 다음칸 인덱스인 9 가 된다.

​참고로 python은 이진탐색을 하는 빌트인 라이브러리가 별도로 있으며, 이를 사용해서 문제를 풀 수도 있다.

# python
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect_left(nums, target)

본래 bisect 라이브러리를 임포트해야 하나, leetcode 에서는 자동으로 임포트를 해준다. bisect 라이브러리 구체적 명세는 python 도움말을 참고하길 바란다.