🎲[알고리즘] Lower bound / Upper bound

Lower bound

• 정렬된 배열에서 찾고자 하는 값(key) 이상의 값이 처음 나타나는 위치.

# Lower bound
# nums[k-1] < key 이고, key <= nums[k]인 k를 찾는다.

def lower_bound(nums, key):
    
    left, right = 0, len(nums)-1
    
    while left < right:  #left와 right가 만나는 지점이 key값 이상이 처음 나오는 위치
        mid = (left + right) // 2		# 나란히 두개가 남았을 때 mid가 왼쪽이므로,
        								# 오른쪽(right)을 mid와 같게해주어야 무한루프에 빠지지 않는다.
        
        if key <= nums[mid]:
         	right = mid		# 이 갱신을 통해, right에 해당하는 값은 key 보다 '이상'임을 보장한다.
        else:
           left = mid + 1

    
    return right			# 보장된 값에 대한 인덱스를 반환한다.

Upper bound

• 정렬된 배열에서 찾고자 하는 값(key)을 초과하는 값이 처음 나타나는 위치.

# Upper bound
# nums[k-1] <= key 이고, key < nums[k]을 만족하는 최소 k를 찾는다.

def upper_bound(nums, key):

    left, right = 0, len(nums)-1

    while left < right:  #left와 right가 만나는 지점이 key값을 초과하는 값이 처음 나오는 위치
        mid = (left + right) // 2		# 나란히 두개가 남았을 때 mid가 왼쪽이므로,
        								# 오른쪽(right)을 mid와 같게해주어야 무한루프에 빠지지 않는다.

		if key < nums[mid]:		
        	right = mid		# 이 갱신을 통해, right에 해당하는 값은 key을 '초과'한 값임을 보장한다.
        else:
            left = mid + 1 

    return right			# 보장된 값에 대한 인덱스를 반환한다.