Binary Search : lower bound & upper bound
Binary Search (이진 탐색)
- 이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다.
- 기준 값을 통해 그 값을 기준으로 데이터를 나누어 탐색한다.
- 중복된 데이터가 없을 때는 기본적인 이진 탐색을 통해 쉽게 구할 수 있으나, 중복된 데이터들이 있는 경우엔 구할 수 없다.
- 이를 위해서는 lower bound와 upper bound를 통해 탐색해야 한다.
lower bound : 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치 탐색 가능
upper bound : 데이터 내에서 특정 값보다 처음으로 큰 값이 나오는 위치 탐색 가능
lower bound : 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치 탐색 가능
upper bound : 데이터 내에서 특정 값보다 처음으로 큰 값이 나오는 위치 탐색 가능
- 참고 : cherishee's tistory
Lower bound
- lower bound는 같거나 큰 값이 처음 나오는 위치를 return해야 하므로, 존재하지 않는 큰 수가 있는 경우 end를 n-1로 했을 경우, 배열의 마지막 인덱스를 넘겨준다.
- 따라서 end를 n으로 하여, 존재하지 않는 수에 대해서는 아예 인덱스 범위에서 벗어난 수를 반환하도록 한다.
- 기본 이진탐색과 다른 점은 값을 찾았을 때, 바로 return 하지 않고, 처음으로 나온 값을 찾기 위해 범위를 좁혀가며 찾는다.
- 그래서 end = mid로 놓고 범위를 좁혀간다.
def lower_bound(goal):
start = 0
end = n
while (start < end):
mid = (start + end) // 2
if goal <= arr[mid]:
end = mid
else:
start = mid + 1
return start
Upper bound
- lower bound와 거의 유사하다.
- 단, 최초로 큰 값이 나오는 곳을 찾기위해 범위를 좁혀간다.
- 주의 : 마지막 값의 인덱스를 찾는 것이 아니다.
def upper_bound(goal):
start = 0
end = n
while (start < end):
mid = (start + end) // 2
if goal >= arr[mid]:
start = mid
else:
end = mid + 1
return start
Author And Source
이 문제에 관하여(Binary Search : lower bound & upper bound), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@nathan29849/Binary-Search-lower-bound-upper-bound
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def lower_bound(goal):
start = 0
end = n
while (start < end):
mid = (start + end) // 2
if goal <= arr[mid]:
end = mid
else:
start = mid + 1
return start
- lower bound와 거의 유사하다.
- 단, 최초로 큰 값이 나오는 곳을 찾기위해 범위를 좁혀간다.
- 주의 : 마지막 값의 인덱스를 찾는 것이 아니다.
def upper_bound(goal):
start = 0
end = n
while (start < end):
mid = (start + end) // 2
if goal >= arr[mid]:
start = mid
else:
end = mid + 1
return start
Author And Source
이 문제에 관하여(Binary Search : lower bound & upper bound), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nathan29849/Binary-Search-lower-bound-upper-bound저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)