[Python] bisect 함수를 통해 이진탐색 구현하기

이번 글에서는 파이썬 언어에서 bisect 함수를 통해서 이진탐색을 구현한다.

1. Bisect 함수

리스트 lst와 숫자 x가 있을 경우(lst는 정렬되어 있다고 가정한다),

x가 lst의 어느 위치에 들어가야 정렬된 리스트가 유지되는지 반환한다.

from bisect import bisect

lst = [1,3,5,7,9]
x = 7

# lst에 '7'이라는 값이 어디에 들어가야 정렬된 리스트를 유지하는지
bisect(lst,x)
# 4라는 인덱스값을 반환함

2. Bisect의 네가지 케이스

2.1 동일한 값이 있을 경우

lst에 동일한 값이 있기 때문에 '7'의 다음 인덱스인 4를 반환한다.

lst = [2,3,5,7,9]
x = 7

bisect(lst,x)
#=> 4

2.2 동일한 값이 없을 경우

lst에는 숫자 '8'이 없다.

이때 '8'이라는 값은 7과 9 사이에 들어가야 정렬된 리스트를 유지하기때문에,

인덱스 4를 반환한다.

lst = [2,3,5,7,9]
x = 8

bisect(lst,x)
#=> 4

2.3 동일한 값이 없고, 주어진 값이 리스트의 최소값보다 작을 때

lst의 최소값은 '2'인데 주어진 숫자는 '1'이다.

맨앞에 삽입되어야 정렬을 유지하기에 인덱스 0을 반환한다.

lst = [2,3,5,7,9]
x = 1

bisect(lst,x)
#=>0

2.4 동일한 값이 없고, 주어진 값이 리스트의 최대값보다 클 때

lst의 최대값은 '9'인데 주어진 숫자는 '20'이다.

맨뒤에 추가되어야 정렬을 유지하기에 인덱스 5를 반환한다.

이때 lst의 인덱스는 4까지임을 명시해야한다.

lst = [2,3,5,7,9]
x = 20

bisect(lst,x)
#=> 5

3. Bisect를 이용한 이진탐색 구현

3.1 같은값 찾기

리스트(lst)에 찾고자하는 값이 있다면 해당 인덱스를 반환하고,

없다면 -1을 반환하여라.

from bisect import bisect

# 주어지는 정보
nums = [1,3,5,6,8,10,15]
x = 4

# 정답값을 담을 변수
result = None

# bisect로 x에 해당하는 인덱스 값 반환
re_idx = bisect(nums,x)

# 만약 리스트에 있는 값보다 작은 경우
# 혹은 첫 값과 같은 경우
if re_idx == 0:
    if x == nums[0]: # 첫값과 같은 경우
        result =  x
    else: # 리스트에 있는 값보다 작은 경우
        result = -1

# 리스트에 있는 값보다 큰 경우
elif re_idx == len(nums):
    result = -1

# 그외의 일반상황일 경우,
# 반환된 인덱스와 전 인덱스의 값을 비교해서 근사값 검출
if nums[re_idx-1] == x:
    result = x
else:
    result = -1

# 정답값 출력
print(result)

3.2 근사값 찾기

리스트(lst)에 찾고자하는 값(x)가 있다면 해당 값을 반환하고,

없다면 가장 근사한 값을 반환하여라.

※동일하게 근사한 값이 두개 존재한다면, 그중 작은 값을 반환해라.

from bisect import bisect

# 주어지는 정보
nums = [1,3,5,6,8,10,15]
x = 3

# 정답값을 담을 변수
result = None

# bisect로 x에 해당하는 인덱스 값 반환
re_idx = bisect(nums,x)

# 만약 리스트에 있는 값보다 작은 경우
# 혹은 첫 값과 같은 경우
if re_idx == 0:
    result = nums[0]
# 리스트에 있는 값보다 큰 경우
elif re_idx == len(nums):
    result = num[-1]

# 그외의 일반상황일 경우,
# 반환된 인덱스와 전 인덱스의 값을 비교해서 근사값 검출
left_n = nums[re_idx-1]
right_n = nums[re_idx]

# 좌측 값이 더 근사할 경우
if abs(left_n - x) < abs(right_n - x):
    result = left_n
# 우측 값이 더 근사할 경우
elif abs(left_n - x) > abs(right_n - x):
    result = right_n
# 두값의 근사치가 동일할 경우 좌측값을 반환
elif abs(left_n - x) == abs(right_n - x):
    result = left_n
    
# 정답값 출력
print(result)