Lower Bound와 Upper Bound는 이진탐색을 기반으로 경계값을 찾는 알고리즘이다.
📕Lower Bound
찾고자 하는 값과 같거나 큰 값이 최초로 나타나는 위치. 즉, 특정 값의 시작 위치를 찾는 알고리즘.
<로직>
이진탐색 시 mid 값이 target 값보다 작으면 left 값을 mid + 1로,
mid 값이 target 값보다 크다면 right 값을 mid로 한다.
반복이 끝나면 right 값이 lower bound가 된다.
int binarySearch(int left, int right, int target) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (lis[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
📘Upper Bound
특정 값보다 처음으로 큰 값의 위치를 찾는 알고리즘
<로직>
이진탐색 시 mid 값이 target 값보다 작거나 같으면 left 값을 mid+1로,
mid 값이 target 값보다 크다면 right 값을 mid로 한다.
반복이 끝나면 right 값이 lower bound가 된다.
int binarySearch(int left, int right, int target) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (lis[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
'BOJ 백준 > 이분탐색' 카테고리의 다른 글
[BOJ] 12015번: 가장 긴 증가하는 부분 수열 (0) | 2023.08.22 |
---|---|
[BOJ] 2565번: 전깃줄 (0) | 2023.08.22 |
[BOJ] 1920번: 수 찾기 (0) | 2022.04.19 |
[BOJ] 2805번: 나무 자르기 (0) | 2021.07.29 |
Lower Bound와 Upper Bound는 이진탐색을 기반으로 경계값을 찾는 알고리즘이다.
📕Lower Bound
찾고자 하는 값과 같거나 큰 값이 최초로 나타나는 위치. 즉, 특정 값의 시작 위치를 찾는 알고리즘.
<로직>
이진탐색 시 mid 값이 target 값보다 작으면 left 값을 mid + 1로,
mid 값이 target 값보다 크다면 right 값을 mid로 한다.
반복이 끝나면 right 값이 lower bound가 된다.
int binarySearch(int left, int right, int target) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (lis[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
📘Upper Bound
특정 값보다 처음으로 큰 값의 위치를 찾는 알고리즘
<로직>
이진탐색 시 mid 값이 target 값보다 작거나 같으면 left 값을 mid+1로,
mid 값이 target 값보다 크다면 right 값을 mid로 한다.
반복이 끝나면 right 값이 lower bound가 된다.
int binarySearch(int left, int right, int target) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (lis[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
'BOJ 백준 > 이분탐색' 카테고리의 다른 글
[BOJ] 12015번: 가장 긴 증가하는 부분 수열 (0) | 2023.08.22 |
---|---|
[BOJ] 2565번: 전깃줄 (0) | 2023.08.22 |
[BOJ] 1920번: 수 찾기 (0) | 2022.04.19 |
[BOJ] 2805번: 나무 자르기 (0) | 2021.07.29 |