bisect_left, bisect_right 구현하기
bisect_left는 sorted array랑 target값이 주어졌을 때
1. target값이 있으면 제일 첫번째 target값의 인덱스
2. target값이 없으면 target값이 삽입되어야 될 곳의 인덱스
를 리턴하는 함수다.
즉 target값이 삽입될 수 있는 인덱스 후보중에 가장 첫 번째 인덱스를 반환한다. (마지막 인덱스를 반환하면 bisect_right)
구현
def bisect_left(lst, target):
l = len(lst)
if l == 0:
return 0
low = 0
high = l-1
while True:
if low >= high:
break
mid = (low + high) // 2
if lst[mid] >= target:
high = mid - 1
else:
low = mid + 1
if lst[low] < target:
return low + 1
else:
return low
이렇게하면 off-by-one 에러 없이 잘 돌아가는데 나도 이게 왜 돌아가는건지 모르겠다 ㅋㅋㅋ;;
근데 코드가 좀 지저분하다.
다른 사람의 블로그를 슬쩍 보자
def bisect_left(arr, value, begin, end):
if begin >= end:
return begin
mid = begin + (end - begin) // 2
if arr[mid] < value:
return bisect_left(arr, value, mid + 1, end)
else:
return bisect_left(arr, value, begin, mid)
이진탐색 - Binary Search #1 (zygygy.github.io)
(지금부터는 내가 위 블로그를 참고해서 bisect_left와 right를 구현해가는 과정이다. 에러가 발생했고 그 에러를 고치는 과정도 포함. 최종 코드는 쭉 밑으로 가면 있다)
자괴감이 들지 않을 수가 없는 깔끔한 구현.
반복문으로 바꿔보자
def bisect_left(lst, target):
low = 0
high = len(lst)-1
while True:
if low >= high:
return low
mid = (low + high) // 2
if lst[mid] >= target:
high = mid
else:
low = mid + 1
중앙값이 target보다 크거나 같은경우, 즉
1. low ... mid==target ... high
2. low. ... target ... mid ... high
high를 mid로 낮췄다. mid-1이 아니다. mid다. 이것 때문에 low와 high는 엇갈리지 않는다.
중앙값이 target보다 작을 경우 즉
low .... mid .... target ... high
인 경우에는 low를 mid+1로 높였다.
low==high가 됐을 때 바로 리턴하면 된다. low가 target값 보다 작지는 않기 때문. target값보다 작은값들중 제일 오른쪽 값 인덱스+1이 된다.
이 함수는 중복값이 많을 때 어떻게 첫번째 값을 찾아낼까?
target이 5일때 중복되는 5가 많은 배열이 들어온다면?
ex ) 1,2,5,5,5,5,5,5,5,5,5,7,8
비밀은 target값과 중앙값이 같을때 하는 행동에 있다. 둘이 같을 때 high를 낮춰버리면 bisect_right가 되고 low를 올려버리면 bisect_left가 된다.
그래서 bisect_right를 구현을 한번 해볼라고했는데
def bisect_right(lst, target):
low = 0
high = len(lst)-1
while True:
if low == high:
return low
mid = (low + high) // 2
if lst[mid] <= target:
low = mid + 1
elif lst[mid] > target:
high = mid
에러가 난다.. 왜지?
array = [5,5] , target=5인경우 2가 나와야 되는데 1이 나오네 ㅋㅋ..
아오 off-by-one 진짜;;
삽입위치라는게 그 위치에 있던걸 오른쪽으로 밀어내고 삽입하는거라서 bisect_left인 경우엔 [5,5]와 5가 주어졌을때 0이 나와도 되는데 bisect_right는 [5,5]와 5가 주어지면 1이 나오면 안된다. ㅋㅋㅋㅋㅋㅋㅋㅋ 아니 근데 예외처리 해봤는데도 안되네? 아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ ㅉㅏ증낰ㅋㅋㅋㅋ........
문제점을 찾았다.
high를 len(lst)-1이 아니라 len(lst)로 초기화 해야된다. bisect_left랑 right 둘다.
자, [5,5,5]랑 6이 주어지면? 인덱스 3이 나와야된다. bisect left나 right 둘다 마찬가지로.
근데 high를 len(lst)-1로 초기화하면 인덱스 3이 아니라 2가 나온다. 알고리즘 특성상 high보다 높은 인덱스가 나올수 없다.
그니까그니까.. 배열 맨 마지막 끝이 삽입 위치가 되는 경우를 고려하려면 high를 len(lst)로 둬서 리턴값이 len(lst)가 될수있게 해야된다는거다..
최종적인 구현이다. 아래 코드는 파이썬의 bisect_left bisect_right와 정확히 같은 동작을 한다.
def _bisect_left(lst, target):
low = 0
high = len(lst)
while True:
if low >= high:
return low
mid = (low + high) // 2
if lst[mid] >= target:
high = mid
else:
low = mid + 1
def _bisect_right(lst, target):
low = 0
high = len(lst)
while True:
if low >= high:
return low
mid = (low + high) // 2
if lst[mid] <= target:
low = mid + 1
else:
high = mid
근데 아직 해결되지 않은 의문. 왜 low = mid + 1, high = mid지?
low = mid, high = mid -1 하면 안되나? 머리 터질거같네ㅠ 오늘은 여기까지..
구현도 제대로 못하겠는데 이걸 다 이해하고 잘 활용해먹는 사람들은 신인가? 자괴감+1 적립