이분탐색 구현 (Python)

 오랜만에 bisect 함수쓰면서 bisect함수랑 이분탐색을 훑어봐야지 하는 생각이 들더라구요. 

그래서 문제를 하나 내고 1부터 1000,000,000까지의 값 중 임의값 찾기라는 임시문제를 내고 코드를 만들어 봤습니다.

 

먼저 파이썬의 bisect 라이브러리입니다.

import bisect

arr = range(1, 1000000000)
idx = bisect.bisect_right(arr, 11)
print(arr[idx])
# output: 12

arr = range(1, 1000000000)
idx = bisect.bisect(arr, 11)
print(arr[idx])
# output: 12

arr = range(1, 1000000000)
idx = bisect.bisect_left(arr, 11)
print(arr[idx])
# output: 11

 

bisect에서는 이렇게 3가지를 잘 사용하는데 bisect랑 bisect_right는 똑같다는 걸 알 수 있어요. 또 bisect_left가 제대로된 값을 찾을 수 있는데요, 이게 둘의 차이점이 제대로된 값을 찾을 수 있다는데서 중요한게 아니라 찾은 값에서 똑같은 값이 있을 경우, 맨 왼쪽을 가르키거나 맨 오른쪽을 가르킨다는 것에 초점을 두고 있습니다.

 

두 번째는 이분탐색 구현입니다.

arr = range(1, 1000000000)

def bisect(arr, x):
    s = 0
    e = len(arr) - 1
    def recursive(s, e):
        m = (s + e) // 2
        print(s, e)
        if s >= e:
            return s
        if arr[m] >= x:
            return recursive(s, m - 1)
        if arr[m] < x:
            return recursive(m + 1, e)
    return recursive(s, e)

idx = bisect(arr, 11)
print(arr[idx])

 

구현한 것을 보면 위와는 조금 다르다는 걸 알 수 있는데요, 일단 중복되는 숫자에 대한 left, right를 선정하는 코드가 없죠. right와 left를 선정하려면 좀 더 다른 코드가 추가되어야하는데 distinct한 arr에는 이렇게 구현해서 쓰는 것도 무리없어 보입니다. 이렇게 이분탐색을 구현해보았고, 다음에도 생각나는대로 한 개씩 되짚어보는 시간을 가져야겠어요.

 

복습 끝