bisect_left, bisect_right 구현

이진정렬 문제를 풀때, underbounded , upperbounded에 대한 개념이 명확하지 않아, 관련문제가 자꾸 헷갈려 직접 구현하며 개념을 정리하려 합니다.

 

bisect_left

arr = list(map(int,input().split()))

def bisect_left(k):
	lo = 0
	hi = len(arr)-1
	while lo<hi:
		m = (lo+hi)//2
		if arr[m] < k:
			lo = m +1
		else:
			hi = m
	return lo
	
#1 2 2 4 8 9
for i in range(1,11):
	print(i,bisect_left(i))

결과:

결과를 보면 찾는 숫자가 한개 이상있다면 그중 가장 왼쪽의 자리를 (하나라면 그자리) ,

없다면 그보다 작은값과 큰값 사이에 들어가는데 이때 자기보다 큰 숫자들을 오른쪽으로 밀고 그자리를 반환한다.

다만 이때 가장큰값보다 큰값이 주어지면 마지막 자리를 반환한다.

 

 

bisect_right

arr = list(map(int,input().split()))

def bisect_right(k):
	lo = 0
	hi = len(arr)-1
	while lo<hi:
		m = (lo+hi)//2
		if arr[m] > k:
			hi = m
		else:
			lo = m +1
	return lo
	
#1 2 2 4 8 9
for i in range(1,11):
	print(i,bisect_right(i))

결과 :

결과를 보면 찾는 숫자가 있다면 그 오른쪽의 위치를 반환하는것을 알 수 있다.(두개이상이라면 맨오른쪽 옆)

다만 이번에도 맨마지막숫자 또는 그보다 큰수가 들어오면 최대값인 마지막자리를 반환한다