LowerBound와 UpperBound는 모두 이진탐색(BinarySearch)을 응용한 알고리즘이다.
일반적으로 이진탐색은 찾고자 하는 값이 정확히 없다면 탐색을 실패한다.
하지만 LowerBound와 UpperBound는 범위에 초점이 맞춰져 있어, 같은 원소가 여러개 있더라도 사용할 수 있다.
개념은 알지만 구현 시 자주 헷갈리므로 정리해보자.
LowerBound
동작방식
LowerBound는 찾고자 하는 값 이상의 값이 처음으로 나타나는 인덱스이다.
LowerBound의 동작 방식은 다음과 같다.
- 초기에 left는 배열의 시작 위치, right는 배열의 길이로 세팅한다
- right가 배열의 끝 위치가 아니라, 길이로 처음에 셋팅한다는 점에 유의하자
- 중간 값(mid)를 가져온다.
- 중간 값과 검색 값을 반복적으로 비교한다.
- 중간 값이 검색 값보다 작으면, left 값을 mid + 1로 셋팅한다
- 중간 값이 검색 값보다 크거나 같으면, right 값을 mid 로 셋팅한다.
- left ≥ right가 되기 전 까지 2, 3번을 반복한다.
예를 들어 다음과 같은 배열이 있다고 하자.
arr = [1, 2, 2, 3, 3, 3, 5, 6, 8]
이 배열에서 검색 값을 3으로 하고, 3 이상의 값이 처음으로 나오는 lower bound를 찾는다고 해보자
- 초기에 left = 0, right = 9가 된다.
- mid = (left + right) / 2 = 4 가 된다.
- 검색 값 3이 arr[mid] 값인 3과 같으므로, right = mid = 4 가 된다.
- mid = (left + right) / 2 = (0 + 4) / 2 = 2 가 된다.
- arr[mid] = 2 이므로 찾고자 하는 값 3보다 작다. 따라서 left = mid + 1이 되어, left = 3이 된다.
- mid = (left + right) / 2 = (3 + 4) / 2 = 3 이 된다.
- arr[mid] 값이 찾고자 하는 값 3과 같으므로 right = mid = 3이 된다
- left값이 right값과 같기 때문에 루프가 종료되고, right값인 3이 lowerbound가 된다.
구현
이를 정리하면 다음과 같은 코드로 구현할 수 있다.
func lowerBound(_ arr: [Int], _ k: Int) -> Int {
var left = 0, right = arr.count
while left < right {
let mid = (left + right) / 2
if arr[mid] < k {
left = mid + 1
} else {
right = mid
}
}
return right
}UpperBound
UpperBound는 찾고자 하는 값 초과의 값이 처음으로 나타나는 인덱스를 말한다.
동작방식
UpperBound의 동작 방식은 다음과 같다.
- 초기에 left는 배열의 시작 위치, right는 배열의 길이로 세팅한다
- 이는 LowerBound와 마찬가지 이다.
- 중간 값(mid)를 가져온다.
- 중간 값과 검색 값을 반복적으로 비교한다.
- 중간 값이 검색 값보다 작거나 같으면, left 값을 mid + 1로 셋팅한다
- 중간 값이 검색 값보다 크면, right 값을 mid 로 셋팅한다.
- left ≥ right가 되기 전 까지 2, 3번을 반복한다.
lowerBound 예시와 마찬가지로 다음과 같은 배열이 있다고 하자.
arr = [1, 2, 2, 3, 3, 3, 5, 6, 8]
이 배열에서 검색 값을 3으로 하고, 3을 초과하는 값이 처음으로 나오는 upper bound를 찾는다고 해보자
- left = 0, right = 9, mid = (left + right) / 2 = 4로 셋팅된다
- 검색 값 3이 arr[mid]값과 같기 때문에 left = mid + 1 = 5가 된다
- mid 값을 구하고 검색 값 3과 비교한다
- mid = (left + right) / 2 = (5 + 9) / 2 = 7
- mid = (left + right) / 2 = (5 + 9) / 2 = 7
- 검색 값 3이 arr[mid] 값인 6보다 작으므로, right = mid = 7로 셋팅한다.
- mid = (left + right) / 2 = (5 + 7) / 2 = 6이 되고 검색 값 3과 비교한다.
- arr[mid] 값이 검색 값 3보다 크므로 right = mid = 6으로 셋팅한다.
- mid = (left + right) / 2 = (5 + 6) / 2 = 5 가 되고, 검색 값 3과 비교한다.
- arr[mid] 값이 검색 값 3과 같으므로, left = mid + 1 = 6 으로 셋팅된다.
- left와 right값이 같아져서 반복이 종료되고, right값인 6이 upper bound가 된다.
구현
lower bound와 코드는 유사하나, 조건식에서의 차이가 있다.
lower bound는 현재 배열의 mid 인덱스 값이 검색 값보다 작을때 left = mid + 1, 크거나 같을 때 right = mid 로 셋팅하지만,
upper bound는 현재 배열의 mid 인덱스 값이 검색 값보다 작거나 같을 때 left = mid + 1, 클 때 right = mid로 셋팅한다
func upperBound(_ arr: [Int], _ k: Int) -> Int {
var left = 0, right = arr.count
while left < right {
let mid = (left + right) / 2
if arr[mid] <= k { // lower bound와 다른 부분은 이곳에 등호가 들어간다는 것
left = mid + 1
} else {
right = mid
}
}
return right
}
참조
https://12bme.tistory.com/120
https://yoongrammer.tistory.com/105
Uploaded by N2T
