Lower bound, Upper bound (python)
📙 Lower bound / Upper bound
# Lower bound
# 정렬 된 배열(nums)에서 찾고자 하는 값(target) 이상이 처음 나타나는 위치
# nums[k-1] < target 이고 nums[k] >= target인 k를 찾는다
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right: #left와 right가 만나는 지점이 target값 이상이 처음 나오는 위치
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return right
# Upper bound
# 정렬 된 배열(nums)에서 찾고자 하는 값(target)보다 큰 값이 처음 나타나는 위치
# nums[k] > target 을 만족하는 최소 k를 찾는다
def upper_bound(nums, target):
left, right = 0, len(nums)
while left < right: #left와 right가 만나는 지점이 target값 보다 큰 값이 처음 나오는 위치
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return right
if __name__ == '__main__':
nums = [1,2,2,2,3,5,6,8,9]
print(lower_bound(nums, 3)) #4
print(upper_bound(nums, 3)) #5
📝 bisect모듈
파이썬 모듈 중 bisect에는 lower bound, upper bound의 기능을 하는 함수가 존재한다. 👉사용법 보러 가기
Author And Source
이 문제에 관하여(Lower bound, Upper bound (python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@himinhee/알고리즘-Lower-bound-Upper-bound-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)